文章目录


试题链接

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？
输入描述:

第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。 第二行N个正整数Li表示每根木棍的初始长度。

输出描述:

输出一行一个非负整数表示每根木棍的最大长度。

示例1
输入

5 10
4 4 4 5 3

输出

1

说明

如果长度为2，只能得到2+2+2+2+1=9根，不够；长度为1可以得到4+4+4+5+3=20根，足够。所以答案最大是1。

示例2
输入

5 3
1 2 3 4 5

输出

3

备注:

题解：

二分的模板题吧
我们假设最后结果是ans，那么小于等于ans的答案都是符合条件的（只是不是最大），而大于ans的肯定不行，那ans怎么确定呢？
这里就用到二分，一开始左界left=1，右界right=最长的木棍长度（也可以初始值为1e9+1,因为木棍再长也不可能大于1e9），然后去这段区间的中间值mid，然后判断mid是否符合条件，如果符合条件，说明mid左边的都可以，右边的不一定，右边有可能还有更优的答案，也可以没有，所以left=mid+1,开始探索mid右边的未知区域。但如果不符合条件，说明当前mid右边更不符合，只有左边才存在符合条件，right=mid-1，探索左边区域，一直这样二分找到最佳答案

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+4;
ll l[maxn];
int n,k;

ll sum;
ll check(ll len)
{
   
	sum=0;
	for(int i=1;i<=n;i++)sum+=l[i]/len;
	return sum;
}
int main()
{
   
	
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>l[i];
	ll ans=0;
	ll left=1,right=1e9+1,mid;
	while(left<=right)
	{
   
		mid=(left+right)>>1;
		if(check(mid)>=k)
		{
   
			left=mid+1;
			ans=mid;
		}
		else 
		{
   
			right=mid-1;
		}
	}
	cout<<ans;
	return 0;
}

推荐例题：

NC16462 跳石头
noip day2 T1题目，也是经典的二分题目，刚学二分的可以练练手