「POJ 3666」Making the Grade 题解（两种做法）

0前言

感谢yxy童鞋的dp及暴力做法！

1 算法标签

优先队列、dp动态规划+滚动数组优化

2 题目难度

提高/提高+

CF rating：2300

3 题面

「POJ 3666」Making the Grade 路面修整

4 分析题面

4.1 简要描述

给出数列 $A$, 求非严格单调不上升或单调不下降, 且$S=\sum^N_{i=1}|A_i-B_i|$ 最小的序列$B$，输出$S$

4.2 模型转换

输入$N$, 然后输入$N$个数，求最小的改动这些数使之成非严格递增或非严格递减即可

5 问题分析

以B为非严格单调递增为例

5.0 暴力

我们直接当考虑已经选了$n$个数：

若$n=1，A_1=B_1$时S最小为$|A_1-B_1|$
若$n>1$，前面已经选择了n-1个数，取得了最小值，考虑怎么取第n个数
- 若 $A_i≥B_{i-1}$，$B_i=A_i$显然最优
- 若$A_i< B_{i-1}$
  - $B_i=A_i$
  - 将$B_k,B_{K+1},...,B_i$都赋值为$A_k,A_k+1,...,A_i$的中位数
  口胡证明：
  我们可以将$B_k,B_{K+1},...,B_i$标记在数轴上
  再将$A_k,A_k+1,...,A_i$标记上
  那么，其实S的几何含义就是每一组$A_i$到$B_i$的距离之和
  我们的小学数学也学过绝对值最值问题：
  求$|x-k_1|+|x-k_2|+|x-k_3|...$的最小值
  其实和这里的$S$是没有任何区别的
  所以，我们知道零点分段法可以解决这类问题
  就是取中位数（就是使每个绝对值内部为0的x答案数组的中位数）
  可以使得绝对值之和最小
1. 如果$x$在两个$k$之间,那么无论$x$在哪,距离之和都是这两个$k$的距离
2. 如果在这两个$k$之外,那么距离之和则为两个$k$距离加上两倍的$x$距近的$k$的距离，肯定不会优于于第一种情况
  那么我们只要尽量让$x$在越多的$k$之间即可
  那么最佳解$x$在图中就是$4$,如果$k$的个数为偶数$n$,则是$k_{n/2}和K_{n/2+1}$之间
  综上，选择中位数最佳

5.1 法一 dp（动态规划）

通过综上分析(5.0中)，我们直接暴力模拟肯定是不行的（这个复杂度直接爆掉了）

但是！

我们可以从中得到一个$very$ $important$的结论：

$B$数列中的每个数必定都为$A$数列中的元素

所以，我们可以考虑用$dp$来解决：

阶段：到第$i$位

状态：$dp_{i,j}$表示以$B_j$结尾的$S_{min}$

B数组是A的复制排序处理过后的数组

$\space \space $ $dp[i][j]$表示把前i个数变成不严格单调递增且第$i$个数变成原来第$j$大的数的最小代价

转移方程：$dp_{i,j}=min(dp_{i-1,k})+|A_i-B_j|,其中1≤j≤n,1≤k≤j$

5.2 法二堆（优先队列）

5.2.1 内心思考

现在我们可以重新想一下，既然是需要求非严格单调递增，那么重要的是什么呢？

当前序列的最大值。（这一点应该是肯定的）

最大值？

是不是有什么奇怪的想法了？

...

堆！

所以就简单搞个大根堆吧！

5.2.2 模拟过程

begin...

$\space \space \space \space \space \space $数据：1 3 2 4 5 3 9

i=1:

$\space \space \space \space \space$ 堆：空，a[i]=1，top=空

这个时候堆是空的，肯定要放进去

$\space \space \space \space \space \space$∴把a[i]放入堆中

$\space \space \space \space \space \space$->堆：1 ，a[i]=1，top=1

i=2:

$\space \space \space \space \space \space$堆：1 ，a[i]=3，top=1

这个时候a[i]>top，就是说明满足非严格单调递增

$\space \space \space \space \space \space$∴把a[i]放入堆中

$\space \space \space \space \space \space$->堆：3 1 ，a[i]=3，top=3

i=3:

$\space \space \space \space \space \space$堆：3 1 ，a[i]=2，top=3

这个时候a[i]<top，说明已经不满足非严格单调递增了，那么就需要修改top或者是a[i]的值

最节省的方法肯定花费top-a[i]来进行更改

更改后会得到(a[i],a[i]),(a[i]+1,a[i]+1)....(top-1,top-1),(top,top)这些二元组

这里面肯定是有合法的二元组，肯定也是有不合法的

再引入一个变量：newtop:当前top被pop掉过后的top

我们可以肯定，在上面所有的二元组当中，是有可以满足值≥newtop的，所以这对二元组是一定可以满足非严格单调递增，那么后面的数据也只需要满足数值≥newtop就可以了

所以我们就需要使得这对二元组的数值尽量不对后面的操作产生影响，那么就放入两个最小值，即a[i]。

$\space \space \space \space \space \space$∴把top给pop掉，a[i]和a[i]放入堆中

$\space \space \space \space \space \space$->堆：2 2 1 ，a[i]=2，top=2

这个时候放入两个a[i]是合法的，那么我们就来看一种放入两个a[i]不合法的情况

...

i=6

$\space \space \space \space \space \space$堆：5 4 2 2 1 ，a[i]=3，top=5

按照我们之前讨论的操作进行过后，会是

$\space \space \space \space \space \space$堆：4 3 3 2 2 1 ，a[i]=3，top=4

$\space \space \space \space \space \space$原序列: 1 2 2 4 3 3

这个时候我们可以发现如果是把a[5]改成3，在原序列看上去是不合法的，但是这问题大吗？

不大。

因为我们更改过后的二元组不一定非是3 3，它也可以是4 4，5 5，那么这样就是合法的了，我们把3丢进去的原因就是为了尽量不影响后面的操作，让后面要是进行变化也会变得尽量小，更好维护非严格单调递增

5.2.3 总结

也就是说，我们需要明确，堆里面存的可能不是最终的序列，它里面存的就是当前序列需要满足的最小值。

可以简单看一张图片，理解一下正确性...：

6 实现细节

6.1 法一：dp（动态规划）

6.1.1 滚动数组

从我们的$dp$方程：$dp_{i,j}=min(dp_{i-1,k})+|A_i-B_j|,其中1≤j≤n,1≤k≤j$

灰常容易地阔以算出空间复杂度是$O(n^2)$

这个。。秉承着我们能省则省的原则

看到这个开二维数组$O(n^2)$的空间貌似有点浪费

那怎么去优化空间呢？

又由于我们的$dp$方程中只用到了$i-1$的信息

于是我们下意识地反应：

——用滚动数组优化！

$\space \space$用位运算符&来记录，这样就只用了$0/1$来表示

重复利用，节省空间

$\space\space\space\space$ $i$&$1$的效果和$i$%$2$的效果是一样的，但是$i$&$1$要快一点

$\space\space\space\space$ 且这种方式比直接写$0/1$少了一个不断交换的过程

$\space\space\space\space$ 窝jio得这个东西还是很·····香的

将$i->i$ & $1$，$i-1->(i-1)$&$1$

方程就变成了这样：

$dp[i$&$1][j]=min(dp[(i-1)$&$][k])+|A[i]-B[j]|,其中1≤j≤n,1≤k≤j$

6.1.2 最小值

但是这个复杂度。。

看上去好像是3层循环，就是$O(n^3)$啊

在$n<=2000$ 的时候就已经$game\space over$了，显然不行啊

这个xiao问题应该有手就行吧

其实只要一边更新$min(f[i-1][k])$一般算当前的$f[i][j]$就行

（因为$k$只到$j$）

6.1.3 降序

不严格单调不上升的情况也一样

更加方便的是可以把$B$数组从大到小排序后，做单调不下降的dp就了

6.1.4 时间复杂度

二维DP，所以就是$O(n^2)$

6.2 法二堆（优先队列）

6.2.1 具体操作

以非严格单调递增为例

搞一个大根堆，依次遍历数组

当堆为空的时候直接$push$
当$a[i]≥top$的时候直接$push$
当$a[i]< top$的时候，ans+=top-a[i]，先pop再push两次a[i]（一个用来代替原pop，一个是本身）

那非严格单调递减就是相反的了

最后把两种的$ans$去一个$min$就好了

6.2.2 时间复杂度

堆的一堆操作，所以就是$O(nlogn)$

7 代码实现

7.1 法一：dp（动态规划）

#include<bits/stdc++.h>

using namespace std;

const int N=2e4+2;

int n,f[2][N],a[N],b[N],ans=0x3f3f3f3f;

bool cmp1(int x,int y){

    return x<y;

}//升序

bool cmp2(int x,int y){

    return x>y;

}//降序

void work(){

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

        f[1][i]=abs(a[1]-b[i]);

    }//边界条件

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

        int minn=f[(i-1)&1][1];

        for(int j=1;j<=n;j++){

            minn=min(minn,f[(i-1)&1][j]);//边更新边求

            f[i&1][j]=minn+abs(a[i]-b[j]);

            //滚动数组

        }

    }

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

        ans=min(ans,f[n&1][i]);

    }//求答案

}

int main(){

    scanf("%d",&n);

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

        scanf("%d",&a[i]);

        b[i]=a[i];//拷贝到b数组

    }

    sort(b+1,b+1+n,cmp1);//从小到大

    work(); //dp计算

    sort(b+1,b+1+n,cmp2);//从大到小

    work();//直接就是一样的啊

    printf("%d",ans);//输出最小

    return 0;

}

7.2 法二：堆（优先队列）

#include<bits/stdc++.h>

using namespace std;

int n;

int a[3100];

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);//读入

    priority_queue<int>q;//大根堆，处理非严格单调递增

    int ans=0,sum=0;

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

        if(q.empty())q.push(a[i]);//空

        else{

            if(q.top()<=a[i])q.push(a[i]);//如上解释操作

            else{

                ans+=abs(a[i]-q.top());//加上答案

                q.pop();//弹出

                q.push(a[i]);//放入两次

                q.push(a[i]);

            }

        }

    }

    priority_queue<int,vector<int>,greater<int> >p;//小根堆，处理非严格单调递减

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

        if(p.empty())p.push(a[i]);//空

        else{

            if(p.top()>=a[i])p.push(a[i]);//如上解释

            else{

                sum+=abs(a[i]-p.top());//加上答案

                p.pop();//弹出

                p.push(a[i]);//放入两次

                p.push(a[i]);

            }

        }

    }

    printf("%d",min(ans,sum));

    return 0;

}

十分简单清晰明了

8 总结

最大的收获：就算做不出来也需要想一些可能的做法，说不定就撞对了
新鲜的知识：更优秀的滚动数组写法|堆的奇妙用法
相似的题目：CF #371 div.1 C Sonya and Problem Wihtout a Legend