P4597 序列sequence
题目背景
原题( t{cf13c})数据加强版
题目描述
给定一个序列，每次操作可以把某个数(+1)或(-1)。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。
输入输出格式
输入格式：
第一行输入一个(n)，表示有(n(n leq 5 imes10^5))个数字。
第二行输入(n)个整数，整数的绝对值不超过(10^9)
输出格式：
输出一个数，表示最少的操作次数
发现之前洛谷做过一个类似的。。P2893
chen_zhe的题解并没有看懂。
原题的(N^2)思路比较好想，离散化后直接开到状态里面就可以了。
然后维护一个按时间顺序维护一个完整的非降数列，假设当前维护到位置(i)了
当前数列的末尾为(p)
-
若(ple a_i)
直接加入数列
-
若(p>a_i)
则把(p)和(a_i)作为一个二元组((a_i,p))拿出来，那么一定要花(a_i-p)的代价让这个二元组变得不降
如果不考虑其他情况，那么这个二元组可以取到的值为((a_i,a_i),(a_i+1,a_i+1),dots ,(p,p))
显然取到最小值最好，那么我们就当( t{Ta})取到了最小值，然后把( t{Ta})的最小值放到数列。虽然这时候可能比现在的末尾要小，不过没关系，现在的新末尾也可能会改变。我们就当这个二元组在末尾大于( t{Ta})的最小取值的时候，把( t{Ta})当末尾那么大就可以了。
可以简单的拿一个大根堆维护上述过程。
考虑为什么这样一定可以取到修改前的数，其实也很好理解，毕竟我们二元组取值要么是自己，要么就是某个末尾啊。
Code:
#include <cstdio>
#include <queue>
#define ll long long
std::priority_queue <ll> q;
ll ans=0,a;int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a);
if(!q.empty()&&q.top()>a)
{
ans+=q.top()-a;
q.pop();
q.push(a);
}
q.push(a);
}
printf("%lld
",ans);
return 0;
}
2018.11.7