P4597 序列 sequence
是CF13C Sequence的加强版，\(N\leq 5*10^5\)。
如果想了解\(O(N^2)\)的DP解法请看此文。
给定\(N\)个数，每次操作可以选其中一个数\(+1\)或\(-1\)。请问要让这个数列不降，最少需要多少次操作？
看到数据范围发现不能用\(O(N^2)\)的dp了，需要换一种思路。
我们用类似贪心的方法做，从左往右找\(i<j,a_i>a_j\)（注意\(i,j\)不一定连续，后面就懂了），然后对它们的值进行上调下调。
如上图，我们发现\(10\to 1\)不满足“不降”，需要进行调整。我们想到在\([1,10]\)中找到一个中间点，把这\(2\)个数都移动到中间点。而无论中间点是几，这一操作代价都为\(10-1=9\)。那么我们为了让操作次数尽可能小，我们应该尽可能让中间点往下，即移动到\(1\)。
总结：如果遇到\(x\)在\(y\)后面，而\(x>y\)，我们需要把\(y\)下移到\(x\)的位置。从左到右遍历每条边，重复上述操作即可。
大家可能会有疑惑：如果\(y\)前面的\(z\)，满足\(x<z<y\)，如果把\(y\)下移到\(x\)，就会破坏前面的“不降”：
-
如果\(z\)后面又遇到一个值\(a_i<a_{i-1}\)，而它之前的最小值正是\(z\)，它就会把\(z\)压下去。
但如下图，我们又发现，\(z\)下调后，后边又不满足不降，此时就把\(x\)作为\(z\)循环上面的步骤。
-
如果\(z\)后面没有更低的值，则说明\(y\)没必要降到\(x\)，中间点可以上移到\(z\)也不会影响结果，但在此同时我们让原序列合法了。而中间点只要在\([x,y]\)中间，消耗就相同，所以答案不受影响。
综上，答案不会受下移的影响，尽管序列可能不满足“不降”，但我们可以在消耗不变的情况下调整至满足条件。
接下来就是代码实现。为了维护前面的最大值，我们开一个优先队列。
对于输入的每一个\(x\)：
首先加入\(x\)。
如果遇到\(x<max\)，则\(ans+=max-x\)，然后\(max\)出队列，加入下调后的高度\(x\)。
时间复杂度\(O(N\log N)\)。
虽然加强版空间限制从64MB提升到了125MB，但是这份代码可以过CF的原题，因为空间消耗只有\(\log N\)而已。
注意开long long。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<int> q;
int n,x,ans;
signed main(){cin>>n;while(n--){cin>>x;q.push(x);if(x<q.top()){ans+=q.top()-x;q.pop();q.push(x);}}cout<<ans;return 0;
}
