洛谷 P4597 序列sequence 解题报告

时间:2022-03-15 10:10:38

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