【洛谷】【堆+结论】P4597 序列sequence

【题目背景：】

原题cf13c 数据加强版（就是说原来能用DP做现在不行了QwQ）

【题目描述：】

给定一个序列，每次操作可以把某个数+1-1。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

【输入格式：】

第一行输入一个n，表示有n( n \leq 5*10^5n≤5∗105 )个数字。第二行输入n个整数，整数的绝对值不超过 10^9109

【输出格式：】

输出一个数，表示最少的操作次数

【算法分析：】

切题背景：
chen_zhe大佬改编了这道题目之后吸引了slyz准高一全机房同学的注意

主要是一开始是道紫题想要通过以后强行把它变黑（雾

然后全机房的同学刚了一节课4597无果（中间它突然变成了黑题QwQ）

然后就被隔壁机房的学长学姐拯救了...

对于一个序列，可以看成高度不同的几根线

如：序列{3、 4、 1、 5}可以看做这样

                  ----

     ----

---- 

            ----

3 4 1 5

对于一个大数a和一个小数b，要做的就是在他们之间的任意位置找到一个基准，将大数向下挪到那个基准，小数向上挪到那个基准

移动的距离等价于a - b

由于是非降序列，将a向下移动的距离越多越可以使之后的数字更容易变成非降序列

所以这个基准应该是选择之前的最大数c，

当之前的最大数在[a, b]这个区间内，将a向下移到c并将b向上移到c的距离等价于将a向下移动到b的距离

　　所以就把a移到b就好了

　　而由于之前已经有一个c值，不把a,b移动到c也能保证之后答案的正确性

　　　　而当之后如果有许多个小数的时候，这么做也能保证之后答案的正确性，因为当前的c和当前b在这种情况里应该是同属于[之后的a, 之后的b]的区间内

当之前的最大数比b还要小的时候，b就变成了之前非降序列的一部分，a - b相当于将a向下移动到b

由于c是之前的最大数（也就是说现在的a > c），所以不存在c比a大的情况

然后开个大根堆瞎搞：

对于读进的一个数num，把它push到优先队列里去

如果这个num比之前的最大值maxn（就是堆顶元素）要小的话

　　ans += maxn - num

　　并把maxn弹出，再push进一个num(把maxn移动到了num的位置，这个操作正确性的证明见上面)

【代码：】

 //序列sequence加强版

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 int n;

 long long ans;

 priority_queue<int> q;

 inline int read() {

     int x = , f = ; char ch = getchar();

     while(ch < '' || ch > '') { if(ch == '-') f = -; ch = getchar(); }

     while(ch >= '' && ch <= '')

         x = (x << ) + (x << ) + ch - , ch = getchar();

     return x * f;

 }

 int main() {

     n = read();

     for(int i = ; i <= n; i++) {

         int num = read();

         q.push(num);

         if(num < q.top()) {

             ans += q.top() - num;

             q.pop();

             q.push(num);

         }

     }

     printf("%lld\n", ans);

 }

巴特西

【洛谷】【堆+结论】P4597 序列sequence

最新文章

热门文章