codeforces713C Sonya and Problem Wihtout a Legend

题目链接： codeforces713C Sonya and Problem Wihtout a Legend

(刷新以获取数学公式)

题意

给定一组数，每次可以用\(1\)的代价将一个数\(+1\)或\(-1\)，求将数列变为严格上升的最小代价。

n ≤ 3000

题解

首先将\(a[i]\)变为\(a[i]-i\)就可以将题目转化为不严格上升。

然后注意到一个数变肯定变到原来有的\(a[i]\)中，直接上\(O(n^2)\)的DP就可以通过了

但这样没有什么技术含量。这题是有\(O(nlogn)\)的做法的。

定义函数\(f_i(x)\)为将前\(i\)个数变为严格上升，且保证\(a_{i}≤x\)的最小代价。我们有：

显然，\(f_{i}(x)\)是一个斜率为非正整数的下凸包。

设\(opt(i)\)是最小的\(x\)使得\(f_i(x)\)取到最小值。那么\(opt(i)\)就是斜率从\(-1\)到\(0\)的转折点，我们可以得到：

我们不能直接贪心的原因是\(opt(i)\)不能维护。

那么考虑维护\(f_{i}\)这个下凸包。

假设我们已经得到了\(f_{i-1}\)，现在加入\(a_{i}\)。可以发现，对于\(x﹤a_{i}\)的直线，加入\(a_{i}\)会使斜率\(-1\)，对于\(x>a_{i}\)的直线，加入\(a_{i}\)会使斜率\(+1\)(除非它的斜率已经是\(0\)，那么就不再增加)。

我们用一个priority_queue维护它。堆中第\(i\)大的元素，是斜率由\(-i\)转为\(-i+1\)的转折点的横坐标。

根据这个定义，弹出堆顶使堆中所有元素斜率\(+1\)，加入一个元素使小于它的所有元素斜率\(-1\)

如果\(a_{i} > opt(i - 1)\)，直接将\(a_{i}\)丢进堆即可；

否则，我们会发现加入\(a_{i}\)会使斜率发生断层。

比如，我们将\(a_{i}\)插入到斜率为\(-1\)的直线中间。本应使右边一段斜率变为了\(0\)，而左边那段斜率变成了\(-2\)。

但是事实上，我们将\(a_{i}\)插入，使得左边的斜率\(-1\)。又弹出了\(opt(i - 1)\)，使所有的斜率\(+1\)。这样，原本斜率应该变为\(-2\)的一段斜率还是\(-1\)。

于是就有一个小trick：只需要把\(a_{i}\)再插入一次就可以了。

事实证明这样做是正确的。总复杂度是\(O(nlogn)\)

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;

int n, x;
LL res;
priority_queue<int> Q;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &x);
		x -= i;
		Q.push(x);
		if (Q.top() > x) {
			res += Q.top() - x;
			Q.pop();
			Q.push(x);
		}
	}
	cout << res << endl;
}