古冶区城乡建设局网站,服装设计公司属于什么行业类型,深圳龙岗好玩的地方,卓天商务跨境电商P4597 序列 sequence 给定一个数列#xff0c;每次操作可以使任意一个数1或-1#xff0c;求小的操作次数#xff0c;使得数列变成不降数列. 1.对于前面比当前位的数字大的数#xff0c;设最大数为 xxx #xff0c;当前的数为 yyy ,则对于 xxx 到 yyy 中间的任意数#xf…P4597 序列 sequence 给定一个数列每次操作可以使任意一个数1或-1求小的操作次数使得数列变成不降数列. 1.对于前面比当前位的数字大的数设最大数为 xxx 当前的数为 yyy ,则对于 xxx 到 yyy 中间的任意数两数的转移贡献都是一致的那么对于后面的贡献一定是将最大数变成当前的数更好当然其课调整性只要后面的数不小于 yyy 那么我们就可以在一定的限度内对两数进行调整使得满足后面序列的安排。
2.对于当前的最大值要么是把当前值换成最大值要么是将最大值换成当前值如果最大值比较多的话那么就是将当前值换成最大值但无论怎么样对结果的贡献都是一致的且也具有返回贪心的特点 代码如下
#includeiostream
#includealgorithm
#includecmath
#includequeue
#includecstring
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_queueint q;
signed main(){ios;int n;cinn;for(int i1;in;i)cina[i];int ans0;for(int i1;in;i){q.push(a[i]);if(a[i]q.top()){ansq.top()-a[i];q.pop();q.push(a[i]);}}coutans;return 0;
}
