CF1015D. Walking Between Houses(贪心+构造)1600

2022年7月12日 下午5:15 杂项 , ,

题意

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

思路

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

来看AC的方法(好吧,我觉得上面那种也能ac),先迈大步(n-1),每次使得s-=n-1k--,需要每次都满足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<<" ";
    }
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注