题目描述

有 $n$ 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 $m$ 条长度相同的绳段，求绳段的最大长度是多少。

输入格式

第一行是一个不超过 $1000$ 的正整数 $n$，表示切割之前有 $n$ 条绳子。

第二行是 $n$ 个正整数，表示每条绳子的长度。

第三行是正整数 $m$，代表要切割出 $m$ 条长度相同的绳段。

数据范围

$1 \le$ 每条绳子的长度 $\le 10^9$

$1 \le m \le 1000$

输出格式

绳段的最大长度，若无法切割，输出 “Failed”。

样例

3
5 10 8
2

8

解题思路分析

在上一题切割绳子.3中，我们是从大到小一个个的去测试 a ，这是枚举+测试的算法思路。但是，当 sum/m 很大的时候，要试的数字就很多，就会超时。

我们现在来分析试 a 的值的时候有没有什么优化的方法（这就是要引出的二分答案算法了。）

如果 a 是不行的（也就是说，切不出 m 条长度为 a 的绳子），那么我们可以推论：a+1 也一定是不行的，既然都切不出 m 条长度为 a 的绳子了，更加切割不出 m 条 a+1 的绳子。否则，很诡异，因为我能切出 m 条长度为 a+1 的绳子，那每条绳子都减掉 1，不就是 m 条长度为 a 的绳子吗？所以，用反证法就知道如果 a 不行，那么 a+1 也不行。

反过来，如果 a 行（a>1），那么 a-1 也行，上面已经说了，我把 m 条长度为 a 的绳子全部切段 1，不就成了 m 条长度为 a-1 的绳子了吗？

所以，我们可以想，有某一个值（我们说这个值是 ans），大于 ans 的所有整数都不行，而小于等于 ans 大于 0 的所有整数都行。这个 ans 就是分界点，也是本题的答案。这个情况，和二分右边界查找的情况非常接近，我们是在众多符合条件的方案中，输出最大的那个可行方案。

找到了上述规律之后，我们就可以采用折半查找的思路来找这个临界点 ans。

1. 如果 a=1 都不行，那就不可能有答案（其实，就是 sum<m 的时候）
2. 如果 sum/m 可以，答案就一定是 sum/m ，不可能有更大的可行方案。
3. 否则，ans 一定在 [1,sum/m] 之间，至于是什么，我们开始折半查找
4. 让 mid = (low+high)，如果 mid 可行，那么答案就位于 [mid,high]，否则答案就位于 [low,mid-1]
5. 重复上面的 第 4 步，直到 low 等于 high （或者 high 跑到了 low 的前面），如果 low 可行，就是答案，否则，就没有答案。

上述算法，称为二分答案，它的思路和二分查找类似，但是，验证一个数字行还是不行，还需要套一个方案验证函数（二分查找是没有这个验证函数的）。

完善程序

#include<bits/stdc++.h>
using namespace std;
int l[1001];
long long m,n;
bool check(long long a)
{
	long long cnt=0;
	for(int i=1;i<=n;i++)
	{
		cnt += __填空(1)__;
	}
	return __填空(2)__;
}
int main()
{
	long long sum=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&l[i]);
		sum += l[i];
	}
	scanf("%lld",&m);
	
	long long low=__填空(3)__,high=max(1,sum/m),mid;
	while(__填空(4)__)
	{
		mid = __填空(5)__;
		if(check(mid)) __填空(6)__;
		else __填空(7)__;
	}
	if( check(__填空(8)__) )
		printf("%lld", __填空(8)__);
	else
		printf("Failed");
	
    return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}