win7网站后台无法编辑,网站建设参考的文献,集约化网站建设情况,动态速写网站正题
题目链接:https://www.luogu.org/problemnew/show/P4597 题目大意
一个长度为nnn的序列#xff0c;每次可以将一个数111或−1-1−1。要求
变成一个非降序列出现的数之前都在原序列 解题思路
我们考虑一下贪心#xff0c;由于变成一个非降序列#xff0c;所以肯定越…正题
题目链接:https://www.luogu.org/problemnew/show/P4597 题目大意
一个长度为nnn的序列每次可以将一个数111或−1-1−1。要求
变成一个非降序列出现的数之前都在原序列 解题思路
我们考虑一下贪心由于变成一个非降序列所以肯定越往下越优。
我们将数一个一个加入序列判断答案。
若我们现在最右边的为maxnmaxnmaxn那么右端加入一个数valvalval时。
若val≥maxnval\geq maxnval≥maxn就暂时不需要处理(因为这样也是非降的)
若vallt;maxnvallt;maxnvalmaxn时我们要寻找一个标准ccc。我们发现因为ccc可以是valvalval也可以是maxnmaxnmaxn所以ccc必定是在val∼maxnval\sim maxnval∼maxn之间之后我们发现(c−val)(maxn−c)maxn−val(c-val)(maxn-c)maxn-val(c−val)(maxn−c)maxn−val所以我们让答案加上maxn−valmaxn-valmaxn−val。然后怎么办因为maxnmaxnmaxn最多降低到valvalval但是如果降低到valvalval就可能会导致前面不再非降。那我们暂时定义maxnmaxnmaxn和valvalval升到除了maxnmaxnmaxn的最大的一个数maxn′maxn#x27;maxn′但是如果下次有一个val′lt;maxn′val#x27;lt;maxn#x27;val′maxn′时我们就改变这次降到的地方使其降到val′val#x27;val′和maxn′maxn#x27;maxn′降到的地方。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
priority_queueint q;
int n;
long long ans;
int main()
{scanf(%d,n);for(int i1;in;i){int x;scanf(%d,x);q.push(x);if(xq.top()){ansq.top()-x;q.pop();q.push(x);}}printf(%lld,ans);
}
