CF1015D. Walking Between Houses（贪心+构造）1600

题意

题目链接：Problem - D - Codeforces
输入正整数 $n(2\leq n\leq 2e9)$, $k(1\leq k\leq2e5)$ 和 $s(1\leq s\leq 1e18)$。
在数轴上有 1,2,3,...,n 共 n 个整点（位置），你一开始在 1 上。
每一步你可以移动到任意位置上（但不能原地不动），移动的距离就是两个位置的距离。
问能不能恰好走 k 步，使得移动的距离之和恰好为 s？
若不能，输出 "NO"；否则输出 "YES" 和 k 个数，表示每一步移动之后的位置。

思路

我一开始的思路是计算出一个t使得前面k-1步都输出t，然后最后一步输出最后一步，嗯，有点复杂，没调出来...也不放了。

来看AC的方法（好吧，我觉得上面那种也能ac），先迈大步(n-1)，每次使得s-=n-1和k--，需要每次都满足s在[k,(n-1)k]中，不然是后面是不够达到k次的。

所以一旦不满足，就开始走中步（[2,n-2]]），然后最后都走小步(1)就好。

代码中有一个精髓就是，while(k--)和t = min(s-k,n-1);，
因为一开始进入循环就会执行k--，这个时候s-k的话肯定不会一下走完（因为之前-1），这样总是会留下一步等最后k==0的时候一下走完，然后如果能走大步当然走，然后就走中步/小步。

代码

inline void Case_Test()
{
    cin>>n>>k>>s;
    if (s<k||s>(n-1)*k) {cout<<"NO"<<endl;return;}
    cout<<"YES"<<endl;
    x = 1;
    while (k--)
    {
        int t = min(s-k,n-1);//精髓
        s -= t;
        if (x+t<=n) x += t;
        else x -= t;
        cout<<x<<" ";
    }
}