分蛋糕 题目描述 楼下蛋糕房明天预计接待 � K 位小朋友，每位小朋友都能从蛋糕房领到一块正方形的蛋糕。

蛋糕房老板提前准备了 � N 块蛋糕，其中第 � i 块是长为 � � a i ​ ，宽为 � � b i ​ 的长方形。

为了公平起见，蛋糕房老板从这 � N 块蛋糕中切出 � K 块蛋糕分给小朋友们。切出的蛋糕需要满足：

形状是正方形，边长是整数。

大小相同。

例如一块 6 × 5 6×5 的蛋糕可以切出 6 6 块 2 × 2 2×2 的蛋糕或者 2 2 块 3 × 3 3×3 的蛋糕。

当然小朋友们都希望得到的蛋糕尽可能大，请你计算出最大的边长是多少么？

输入格式 第一行包含两个整数 � N 和 � K。 ( 1 ≤ � , � ≤ 1 0 5 ) (1≤N,K≤10 5 )。

以下 � N 行每行包含两个整数 � � a i ​ 和 � � b i ​ 。 ( 1 ≤ � � , � � ≤ 1 0 5 ) (1≤a i ​ ,b i ​ ≤10 5 )。

输入保证每位小朋友至少能获得一块 1 × 1 1×1 的蛋糕。

输出格式 输出切出的正方形蛋糕的最大可能的边长。

样例 #1 样例输入 #1 2 10 6 5
5 6 样例输出 #1 2 提示

#include<bits/stdc++.h>
using namespace std;

int n, m, t;
const int N = 1e5 + 5;
int s[N];

bool check(int x) {
	int count = 0;
	for (int i = 1; i <= n; i++) {
		count += s[i] / x;
	}
	return count >= m;
}

int binarySearch(int l, int r) {
	long long ans = 0, mid = -1;
	while (l <= r) {
		mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return ans;
}

int main() {
	cin >> n >> m >> t;
	
	int maxx = -1;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		maxx = max(maxx, s[i]);
	}
	
	cout << binarySearch(1, maxx / m + 1) << endl;
	
	return 0;
}