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;
}