题解 P1281 【书的复制】

MuelsyseU · 2019-12-01 13:01:55 · 题解

1. 前言

所以本魔芋最近由于开始学习二分答案，看到自己的思路貌似比较清奇（输出十分奇葩）。

于是立即来这边水一水……

不久前在学习DP魔芋卡在线性动规无法理解，所以这里用二分法。用DP者疑似不能通过UVA714（备用链接vjudge）

因为据老师而言二分答案模版不宜大动，刚开始想的在check中边遍历边调整输出的数组，后来改成在输出时做一check的模拟来方便地输出。

2. 二分答案思想

简述二分答案的基本思想，dalao可跳过

二分答案的理解疑似是来自二分查找 （并不），二分查找的理解疑似是来自“猜数游戏”。

1 2 4 10 29 30 31 65

假设预选一个数作为答案，让玩家每次对其中一个数进行询问。

每个询问可能回答：该数比答案大、比答案小或猜中答案。

如果该数即是答案则游戏结束。

那么，希望用最少的询问次数猜出答案，就可以用二分查找法。

由于数列单调上升，试想先取一中间数如10，如果回答“太小”，则“嫌疑”范围肯定是10-65（方便起见这里把10考虑进去）这一段4个数；如果“太大”则嫌疑范围会取到1-10。

可以再在新的嫌疑范围中取该范围的中间数来询问，比如询问10-65中的30；之后再在新的范围中取中间数……可以预见，最多询问3次（从实际编码角度可能理解为4次）就能确定这个答案。

简单讲讲代码实现。二分，顾名思义要将数据分成两类，比如小于等于X和大于X两类。分类要求不重不漏且满足单调。

定义low和high表示“嫌疑范围”的上下界，由于可知当“嫌疑范围”确定到一点时即结束，所以循环条件为low+1<high。（技巧：初始化low=0,high=n+1）

结束时，可发现数据已被分成了[a[0],a[low]]和[a[high],a[n]]两类。这时就可据low,high找到“最接近X的、次接近X的、大于X且最接近X的”值等。

其实做这道题应该对二分查找有较深理解的，所以这里只是简述一下，接下来不再讲。

二分答案基于二分原理，即用二分的思想快速“猜出”最合适的答案。当且仅当：

1. 题目难以用直接数学方法解出；
2. 题目用逐步验证的方法相对容易解出，但暴力枚举又容易超时；
3. 答案有明显的范围，且范围时间上允许二分答案（时间复杂度一般近似O[log_2(right-left+1)]）；
4. 问题的答案是单调的（反复强调的重点），即当验证答案X满足条件，则[n,right]或[left,n]也一定满足；不满足时，也可表明[left,n]或[n,right]也一定不满足。

满足以上条件时，二分答案就可以使用且可能显著优化时间复杂度。

注意一点，二分答案实际上仍然属于穷举的优化，其基本思路也是需要一个个查找验证，所以check验证函数的编写是二分答案的核心。比较容易地是采用贪心法验证。

由于仍然是需要分界，因此分成可行与不可行两类。比以下模板是最后找到的low就是可行的最大值。

接下来有个无需ans的蒟蒻模版，也就是将一般low=mid+1,high=mid-1改成直接赋值为mid。

实际上可发现mid本身是不需再确定的，所以此模板把时间复杂度略微抬高但较容易理解。

int find(int low,int high) {
    int mid;
    while(low+1<high){          //找到可行与不可行的分界
        mid=low+(high-low)/2;   //此处是(low+high)/2的防爆优化
        if(check(mid))          //check函数检查可行性
            low=mid;            //当可行时[left,mid]也可行
        else
            high=mid;           //当不可行时[mid,high]也不可行
    } 
    return low;                 //由于low表示可行，返回low
}

关于二分答案，最适合练手的个人认为是木材加工。

3. 二分解题思路

关于P1281，可抽象为求将一个数列分成指定份时每份和的“最大值最小”的方案。

从“最大值最小”可以从两个角度看，首先“最大值最小”“最小值最大”一般是二分答案的典型（裸）特征，所以此题的二分思想并不复杂；

另一方面，由于此题显然是一个最优解问题，数据范围不大所以动态规划也是可行的。

前面提过UVA714这个多组数据版，可以发现DP在数据大时中超时几率大，因此正解个人认为是二分答案法。

下面讲此题的基本思路。

注：代码中变量n表示题中m，m表示题中k。

首先明确我们要二分查找什么？这似乎是其它题解几乎没有提到的。顾名思义，要二分的一般是“答案”。

但是此题答案不是一个数，而是在 “抄写页数最多的人” 抄写的页数最少时的具体方案。当我们要求出这个方案时，是不是首先要得到这个最小值？所以可以直接先二分这个值。

现在倒回去看二分答案的四个要素。这个值肯定很难用数学方式或暴力枚举来解(1,2-2)，并且这个最小值也存在范围(3)：从页数最多那本书的页数到所有书页数的和。

这个范围也容易理解。首先任何一本书都必须要被抄写，所以无论如何得有一个人抄写那本页数最多的书；当然，从极端情况下（只有1人抄写），最多可能有一个人抄写完全部的书，而不可能更多。

粗略计算可发现这个范围用二分答案是完全允许的。（大约只需数十次验证）

现在只剩两个要素(4,2-1)，也就是单调性和如何逐步验证。

先考虑单调性。设想我们已经验证，抄写页数最多者的页数的最小值小于等于30页，那么是不是肯定小于等于31页？

再假设已知这个最小值肯定大于11页，那么是不是肯定也会大于10页？

换言之，当某个答案可行时，比它大的答案也肯定可行，无需再验证，上界就可以减小；同理，当某个答案不可行，比它小的答案也肯定不可行，下界就要上移。

所以单调性是完全满足的。

最后考虑，我们如何验证答案是否可行？如前所述，由于我们假想已知这个“抄写页数最多者的页数”，可以使用贪心法。

由于答案本身是最大值，也就是不允许超过的，那么我们可以遍历整个数组，逐个取书给某人抄写，直到发现再抄就会超过上限时，就换下一个人来取。

这样，在遍历结束时，就可知道这个上限对应最少需要多少人抄写。如果这个数量超过了k，即总人数不足抄写完全部的书，表示答案是不可行的；反之，如果这个值小于等于k，这个答案就是可行的。

上述内容有两个细节需提示。首先，按理说，不是需要人数恰好等于k才表示可行吗？

实际上，题中没有强制每人必须有活干（虽然数据隐式转化为满足此条件）。也就是说，假设一部分人抄写就达到最小值，那也就不需要更多的人。

另一个点是遍历的方向。根据上述内容容易看出，这个方法是优先先遍历的人抄写，也就是如果只需一部分人抄写，那么优先让先遍历的人抄得多些。

而对应题中是要求尽可能让前面的人少抄写（走后门？），同时本身数据是升序的（顺便一提，如果不是升序也需排序成升序），所以需要倒序遍历。

至此，我们已理出了二分答案的大部分框架。

4. 二分代码实现

个人比较喜欢把二分玩得清奇一些，所以首先我们看find函数。

向前翻100行回去看二分答案的框架。由上所述，可知在满足条件时移动的是上界，反之移动下界。

由此，十分容易就写出了以下函数：

int find(int low,int high) {
    int mid;
    while(low+1<high){
        mid=low+(high-low)/2;
        if(check(mid))  //检查可行性
            high=mid;   //上界下移
        else
            low=mid;    //否则下界上移
    } 
    return high;        //high表示可行最小值
}

一般二分答案重点就在于check函数。但由于我们上面已理清思路（有不明白可以多读几遍），写起来会发现并不太困难。

设num累计总共所需的人数，t保存当前的人抄写的总页数。由于一开始就有1个人，num初始化为1。

有一个细节要注意，由于我们计算时是不允许超过上限的，所以首先判定当前的人抄写此书是否超出上限，只有在确定不会超出时才进行累加。

顺便提醒一下，注意前面的范围从页数最大值开始，所以保证每本书累加后都不会一本书直接超出上限，即每人至少可抄写一本书。

bool check(int s) {             //传入mid
    int num=1,t=0;              //num=需要人数，t=当前人总页数
    for(int i=n;i>=1;i--) {     //倒序遍历
        if(t+a[i]>s) t=0,num++; //如超出则换下一人
        t+=a[i];                //累加入此书
    }
    return num<=m;              //如果人数足够则答案可行
}

5. 输出

写到这里就不知所云了？

是不是已经忘记题目要求我们输出的：方案？

但是到现在我们只求出了“抄写页数最多的人的页数最小值”。现在，要如何从这个最小值求出具体的方案？

等等！是不是感觉似曾相识？的确，刚刚我们刚打完根据某个“答案”求出具体方案的方法。也就是check函数中的那个倒序循环，正好可用于生成答案。

（实际上，个人感觉其它大部分题解在输出上都复杂化了）

于是，现在我们设置两个数组x[505],y[505]表示各人负责书的起始编号和结束编号。注意，假设前面有部分人不必使用时存储的就是0 0，所以需要初始化为0。

那么我们在何时给这个数组赋值？显然是在“换人”时。也就是在if(t+a[i]>s)的时候。

仔细思考（或试错），由于在此时表示第i本已经不能给当前的人抄写了，所以x[num]=i+1；那么第i本书应归下一人抄写，所以y[++num]=i。

注意，以上均是建立于从后往前遍历的基础上的，所以每个人的结束编号在开始编号之前确定。这里必须花一点时间确保理解。

最后注意一点，由于第一个人的结束编号（即书的总本数）和最后一个人的起始编号（即第一本）无法在循环中设定，所以最后还需增加y[1]=n,x[num]=1。

小结一下，实际上我们完全可以直接复制check中的部分，然后在判断处增加数组的处理，同时前后注意初始化即可获得一个完整的输出数组。

int s=find(low,high);
int t=0,num=1;
for(int i=1;i<=m;i++)
    x[i]=y[i]=0;        //初始化

y[1]=n;                 //第一个人从第n本开始
for(int i=n;i>=1;i--) { //倒序遍历
    if(t+a[i]>s) {      //当前书无法给第num人抄写
        t=0;            //重置
        x[num]=i+1;     //第num人开始编号定为i+1
        y[++num]=i;     //第num+1人结束编号为i
    }
    t+=a[i];
}
x[num]=1;               //最后一个人从第1本开始

最后根据这个数组输出，注意由于数组是倒序的（同样反复强调），所以输出时也应从m到1倒序输出。

for(int i=m;i>=1;i--)   //注意倒序
    cout<<x[i]<<" "<<y[i]<<endl;

6. 总结

参考代码如下（建议开long long）：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

long long n,m;
long long a[505];
int x[505],y[505];              //记录输出

bool check(int s) {             //检查
    int num=1,t=0;
    for(int i=n;i>=1;i--) {     //倒序
        if(t+a[i]>s) t=0,num++; //换下一人
        t+=a[i];
    }
    return num<=m;              //人数是否足够
}

int find(int low,int high) {    //二分
    int mid;
    while(low+1<high){
        mid=low+(high-low)/2;
        if(check(mid))
            high=mid;
        else
            low=mid;
    } 
    return high;                //注意返回high
}

int main() {
    long long low=0,high=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        high+=a[i];             //上界为所有书的和
        low=max(low,a[i]);      //下界为最厚书的页数
    }
    int s=find(low,high);       //获取最优值
    int t=0,num=1;
    for(int i=1;i<=m;i++)       //初始化输出数组
        x[i]=y[i]=0;

    y[1]=n;                     //第一人结束点为n
    for(int i=n;i>=1;i--) {     //倒序
        if(t+a[i]>s) {
            t=0;
            x[num]=i+1;         //第num人开始编号定为i+1
            y[++num]=i;         //第num+1人结束编号为i
        }
        t+=a[i];
    }
    x[num]=1;                   //最后一人起始点为1

    for(int i=m;i>=1;i--)       //倒序
        cout<<x[i]<<" "<<y[i]<<endl;
    return 0;
}

嗯……看起来并不太长？

当然，也可以进行一些花式操作，比如在check中直接调整输出数组，最终由于最后一次check我猜肯定是可行的（不然不会结束），所以至少在[1,m]的范围内答案是正确的。

感觉这个思路最与众不同的地方（仅仅）是输出……虽然魔芋不能理解递归输出（我太蒻了），但是此文也仅算抛砖引玉，顺便聊以复习。

当然还是感谢读完这300行的诸位，希望能对大家有一些帮助，谢谢！

以上。