题解：P11273 「Diligent-OI R1 C」DlgtRank

· · 题解

嗯，还算是简单题吧。

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

依题意得，最大值答案一定是 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);
//码的很繁琐，最好直接用上面的结论，写我这个特别容易写挂谔谔（

注意答案不能为负。