题目描述

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

输入格式

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

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

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

数据范围

1 <= 每条绳子的长度 <= 10^6

1 <= m <= 10^8

输出格式

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

样例

3
5 10 8
2

8

解题思路分析

本题是为二分答案算法做铺垫的。二分答案本质上是一种枚举算法，只不过它是在特定情况下，当答案具有单调性的时候的高效枚举而已。

本题，数据量不算很大，可以先感受一下暴力枚举去解这条题是怎么做。

把每条长绳子切割为长度为 a 的段绳子，一开始，我们从一个很大的值开始试，如果能任务不成功，我们就试一个小一点的数 a-1 (可以理解为 $a_2$ )，当我们发现第一个能切割成功的 $a_i$ 就是本题的答案。

这种比较复杂比较绕的程序，要把当中的一些重复性的逻辑抽取出来，做成一个自定义函数，这样可以使得 main 函数更加简练，更加容易理解。容易理解，就容易检查错误，就容易修改。

完善程序

#include<bits/stdc++.h>
using namespace std;
int l[101],n,m;
填空(1) check(int a) //检查把 n 条绳子切割成 m 条长度为 a 的短绳子是否可行
{
	int cnt=填空(2);
	for(int i=1;i<=n;i++)
	{
		cnt += 填空(3);
	}
	return 填空(4);
}
int main()
{
	long long sum=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&l[i]);
		sum += l[i];
	}
	scanf("%d",&m);
	for(int i=填空(5);填空(6);i--)
	{
		if(check(i))
		{
			printf("%d",填空(7));
			return 0;
		}
	}
	printf(填空(8));
    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) }}