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