rockdu
描述
给定一个长度为 n 的非负整数序列 a[1..n]。
你每次可以花费 1 的代价给某个 a[i] 加1或者减1。
求最少需要多少代价能将这个序列变成一个不上升序列。
输入
第一行一个正整数 n。
接下来 n 行每行一个非负整数，第 i 行表示 a[i]。
1 ≤ n ≤ 500000
0 < a[i] ≤ 109
输出
一个非负整数，表示答案。
样例解释
[5,3,4,5] -> [5,4,4,4]
样例输入
4 5 3 4 5
样例输出
2
本题有一个十分精妙简短的O(N log N)算法。我们定义f(x)为当前数列末尾<=x的最小代价。这样我们一边插入a[i]，一边维护函数，每一次找函数的最低点即可。发现f(x)和x的关系是线性的！并且观察每一次累加的函数为|x - Ai|，这是我们熟悉的绝对值函数折线。因为一条函数与一个单折线相加，实质为拐点取并并且将单折线拐点左右两边的斜率都累加上单折线斜率。这样我们可以维护一个折线的所有拐点的横坐标，每一次的操作有两种情况：
如果新加入的数在当前f(x)最右端拐点的左边，那么对答案没有影响。想象函数的最低点其实没有变。
如果新加入的点在当前f(x)最右端拐点的右边，那么对答案的影响为两点横坐标的差。但是对于新的函数，因为f(x)是数列末尾<=x的代价，所以把末尾的拐点删除，插入当前点即可。
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int > q;
int n, c, ans;
int main() {
scanf("%d", &n);
for(register int i = 1; i <= n; ++i) {
scanf("%d", &c);
q.push(-c);
if(-q.top() < c) {
ans += c + q.top();
q.pop(), q.push(-c);
}
}
printf("%d", ans);
}
没有帐号? 立即注册