自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:05:58，当前版本为作者最后更新于2024-11-10 23:06:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

嗯，还算是简单题吧。

首先拿到题目后很容易想到排序。

依题意得，最大值答案一定是 $0$，因为无论怎么加都一定是第一。

容易发现相同数字的答案一定相同，所以直接忽视已经处理过的数字。（特殊性质 A）

我们可以把原问题转化到数轴上。然后你就会发现这题怎么这么像堵车（

思考发现，当一个数在初始局面下因为前面的一个数堵住时，那么答案将是前面一个数的答案加一，这是容易证明的。（特殊性质 B）

因为每当前面停下，当前数必然也会有一次停下，而且还要额外算上初始局面的一次不可移动。这就和堵车时前面的车动一下你动一下，前面停你也停一样谔谔。

形式化的讲，$ans_i=ans_{i+1}+1$。注意，这里的 $i$ 越大表示越前面，即 $a_{i+1}>a_i$。

好了，那么恭喜你拿到了 $18\text{pts}$ 的高分。

现在让我们来研究初始数据不直接堵住的情况吧。

举个栗子：

（注：$k=1$）

根据上文结论，二号车会被堵一次。

如果一号车被二号车堵的话，那么一号车将会被堵两次。

幸运的是，一号车只有开到 $a_2-1=9$ 的时候，才会被堵。也就是说，在一号车到 $9$ 前，是不会被堵的。

通过计算知道，一号车到 $9$ 要开 $\frac{a_2-a_1-k-1}{k}+1=8$ 次操作。

然后发现等开到的时候都不堵了。所以 $ans_1=0$。

仔细研究栗子以及打个暴力研究多组 hack 后可以发现，一辆车到达堵车的点所用的操作次数，刚好可以抵掉在初始局面就堵的答案。

证明：

显然如果两车同时在运动，它们间的距离将不会改变。

前车堵住了，后车花费一次操作缩短距离，与此同时堵车的次数减一。

然后你会发现，如果距离缩短 $k$，必然会少堵一次车。也就是说答案会减少开上去的操作次数。

那么直接套式子算操作次数和原本的答案即可。

然后做完了。

主体代码：

for(int i=1;i<=n;i++)
    if(a[i].x+k>=a[i-1].x&&a[i].x!=a[i-1].x)
	a[i].ans=a[i-1].ans+1;
    else a[i].ans=max(1ll,a[i-1].ans-max(0ll,a[i-1].x-a[i].x-k-1)/k);
//码的很繁琐，最好直接用上面的结论，写我这个特别容易写挂谔谔（

注意答案不能为负。