P4597 序列 sequence题解

P4597 序列 sequence

给定一个数列，每次操作可以使任意一个数+1或-1，求小的操作次数，使得数列变成不降数列.

1.对于前面比当前位的数字大的数，设最大数为 $x$ ，当前的数为 $y$ ,则对于 $x$ 到 $y$ 中间的任意数，两数的转移贡献都是一致的，那么对于后面的贡献，一定是将最大数变成当前的数更好，当然其课调整性，只要后面的数不小于 $y$ ，那么我们就可以在一定的限度内对两数进行调整，使得满足后面序列的安排。

2.对于当前的最大值，要么是把当前值换成最大值，要么是将最大值换成当前值，如果最大值比较多的话，那么就是将当前值换成最大值，但无论怎么样，对结果的贡献都是一致的，且也具有返回贪心的特点
代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
#define int long long
#define MAXN 10000010
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int a[MAXN];
priority_queue<int> q;
signed main(){ios;int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans=0;for(int i=1;i<=n;i++){q.push(a[i]);if(a[i]<q.top()){ans+=q.top()-a[i];q.pop();q.push(a[i]);}}cout<<ans;return 0;
}