P4597 序列sequence
题目背景
原题\(\tt{cf13c}\)数据加强版
题目描述
给定一个序列,每次操作可以把某个数\(+1\)或\(-1\)。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。
输入输出格式
输入格式:
第一行输入一个\(n\),表示有\(n(n \leq 5\times10^5)\)个数字。
第二行输入\(n\)个整数,整数的绝对值不超过\(10^9\)
输出格式:
输出一个数,表示最少的操作次数
发现之前洛谷做过一个类似的。。P2893
chen_zhe的题解并没有看懂。
原题的\(N^2\)思路比较好想,离散化后直接开到状态里面就可以了。
然后维护一个按时间顺序维护一个完整的非降数列,假设当前维护到位置\(i\)了
当前数列的末尾为\(p\)
-
若\(p\le 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)\)
显然取到最小值最好,那么我们就当\(\tt{Ta}\)取到了最小值,然后把\(\tt{Ta}\)的最小值放到数列。虽然这时候可能比现在的末尾要小,不过没关系,现在的新末尾也可能会改变。我们就当这个二元组在末尾大于\(\tt{Ta}\)的最小取值的时候,把\(\tt{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\n",ans);
return 0;
}
2018.11.7