浅析 NC23049 华华给月月准备礼物 （二分）

题目链接：

https://ac.nowcoder.com/acm/problem/23049

题面：

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

输入描述:
第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行 N 个正整数 L_i，表示每根木棍的初始长度。
输出描述:
输出一行一个非负整数，表示华华最终得到的n根木棍的每根最大长度。

input:
5 10
4 4 4 5 3
output:
1

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

input:
5 3
1 2 3 4 5
output:
1

数据范围:
1 ≤ N ≤ 2×10^5
1 ≤ L_i ≤ 10^9
1 ≤ K ≤10^9

分析：

二分法：

思路：对所有的木棍做从大到小的切割，随着切割长度不断缩小，得到的木棍根数会越来越多。切割长度和对应的木棍根数呈负相关，所以可以使用二分进行检索。

注意二分的条件书写！！！

#include<iostream>
using namespace std;
const int maxn = 2 * 1e5+7;
int n, k;
int a[maxn] = {};

// 二分查找
int main () {
	
	cin >> n >> k;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	int l = 1, r = 1e9;
	
	while (l <= r) {
		int mid = (l + r) >> 1;
		int cnt = 0;
		
		for (int i = 1; i <= n; i++) {
			cnt += a[i] / mid;
		}
		
		if (cnt >= k) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}		
	}
	
	cout << l-1;
	return 0;	
}