CodeForces 1015D Walking Between Houses

题目大意

题目链接 给定n，k，s。 总共k+1个空，第一个空已经填上了1，用不超过n的正整数去填这些空。要求相邻数差的绝对值之和为s且必须保证相邻的数不相同。一个数允许被填多次。 输出一种填法。

题解

构造，还行。

eachstep = s/k得到平均每一步的值，即相邻数之差绝对值的平均值 rest = s%k得到多出来的步数

三种情况会输出 NO：

1. eachstep > n-1说明相邻数之差绝对值的平均值大于n-1了，那显然不可能构造出来；
2. eachstep == n-1 && rest != 0说明相邻数之差绝对值的平均值为n-1，但是余数不为0，表示还差几步到s，因此也构造不出来；
3. eachstep < 1说明相邻数之差绝对值的平均值小于1，要求相邻数不相同，因此这种情况也构造不出来。可能会有人忘掉这个条件吧。

输出YES： 挺常用的一种思路，多出来的这几步（即rest），顺序、均匀分给每两个相邻的数。（顺序是保证后进行跳跃时不会越界，这部分太细节了就不细说了） 用数组保存相邻数之间的差值的绝对值，循环遍历，加或减保存的值进行输出即可。

注意：记得开LL

代码

#include
using namespace std;
typedef long long ll;
const int N = 2e5+10;

ll n, s, rest, eachstep, ans[N];
int k;

int main()
{
	cin>>n>>k>>s;
	ll eachstep = s/k;
	ll rest = s%k;
	
	if(eachstep > n-1 || (eachstep == n-1 && rest) || eachstep