题解 CF713C 【Sonya and Problem Wihtout a Legend】

· · 题解

题意

更好的阅读体验

四倍经验：（前三题为使得序列非严格递增）

P4597 序列sequence

CF13C Sequence

P2893 [USACO08FEB]Making the Grade G

CF713C Sonya and Problem Wihtout a Legend

分析

首先有一个套路的想法，将a_i减去i，这样可以使得求严格递增改为非严格递增，因为我们需要考虑的只是a之间的相对大小关系，因此把a_i减去i并求非严格递增序列之后，我们加回这个i，就可以让相邻两项之间差增加一，变为严格递增。

转化之后，我们考虑如何求解。

考虑下面一种想法（主要是我想不到怎么正向考虑这种诡异的想法，只能强行说明这个做法的正确性）：

我们边维护序列边用优先队列维护当前修改过的序列的最大值，每当我们得到一个数x，我们先把它加入优先队列，然后取出堆顶y（如果有多个最大值，我们取出靠后的），如果x\geqslant y，我们不用管，如果x<y，我们强行把y修改为x（即\text{pop}掉堆顶，并新\text{push}进一个x）。

我们考虑任意一种调整方法,发现对于逆序对x,y(x<y,a_x>a_y)，我们发现y是不可能减小的（否则就更不优了），而我们的算法先钦定了y不减小，所以算法在以后的选择一定会更优，因此我们发现这个代价达到了下界。

然后考虑一个问题：如果y修改为x之后，y前面的最大值z大于y了（即x<z<y），那么这种构造的代价是否不合法？

我们构造到最后，这个z有可能也被修改了，我们不妨讨论z最终的值z'。

我们定义“微调”为不改变花费的情况下，改变某个数对的值。

如果z'>x，那么我们可以强行把x和y强行微调成z'（考虑正确性：因为x<z<y，所以在进行x和y的强行修改时可以用一种反悔的思想将x和y同时改成z'，此时花费仍然为(y-z')+(z'-x)=y-x），这样z和x,y的矛盾就不存在了。

如果z'\leqslant x，那么我们发现它与x和y不再存在矛盾，而它之前的数与它的矛盾可以用类似归纳法一样的方式证明微调可以使得花费不变。

时间复杂度：O(n\log n)。

代码

#include<stdio.h>
#include<queue>
using namespace std;
int n;
long long ans;
priority_queue<int>q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        x-=i,q.push(x);
        if(x<q.top()){
            ans+=q.top()-x;
            q.pop(),q.push(x);
        }
    }
    printf("%lld\n",ans);
    return 0;
}