自动搬运

查看原文

来自洛谷，原作者为

	MuelsyseU 行き場のない声の淵か 赤い水が流れ落ちるのら

搬运于2025-08-24 21:23:18，当前版本为作者最后更新于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$行的诸位，希望能对大家有一些帮助，谢谢！

以上。