CF713C Sonya and Problem Wihtout a Legend解题报告

解题报告

CF713C Sonya and Problem Wihtout a Legend解题报告：

更好的阅读体验

题意

• 给定一个长为$n$的序列$a$，可以进行若干次操作使得某个数减一或加一，求使序列严格递增的操作数；
• $1\leqslant n\leqslant3000$。

四倍经验：（前三题为使得序列非严格递增）
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;
}