题意
题目链接: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<<" ";
    }
}