P4597 序列 sequence
CF713C Sonya and Problem Wihtout a Legend
用于描述一系列问题类似在一条序列上每次加一或减一，使他的原序列变成一条非降序列，求最小次数的问题。
开个小根堆，对当前值 \(x\) ，每次将读入的数放进堆中，对顶维护当前最大值，出现不合法情况，即存在逆序对，我们就用 \(top()-x\) 的代价将逆序对消除，再将已经变成 \(x\) 的 \(y\) 入队，就可以在 \(O(n \log n)\) 的时间内解决。
P4597 Code.
#include<bits/stdc++.h>
using namespace std;
int n; long long res; priority_queue<int> q;
int main()
{
scanf("%d",&n);
while(n -- )
{
int x; scanf("%d",&x); q.push(x);
if(x < q.top()) res+=q.top()-x,q.pop(),q.push(x);
}
printf("%lld",res);
return 0;
}
下面这一道题略有不同，题目让求一个严格递增的序列，我们考虑一个套路的转化，将 \(a_i\) 减去 \(i\) ，就可以从严格递增序列变成非严格递增序列了，再同上面操作一下就可以了。
CF713C Code.
#include<bits/stdc++.h>
using namespace std;
long long res; int n; 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()) res+=q.top()-x,q.pop(),q.push(x);
}
printf("%lld",res);
return 0;
}