分巧克力
原题目链接
问题描述
儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hᵢ × Wᵢ 的长方形。为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
要求切出的巧克力满足以下条件：
- 形状是正方形，边长是整数；
- 大小相同。
例如：一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力，或者 2 块 3×3 的巧克力。
所有小朋友都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少吗？
输入描述
- 第一行包含两个整数
N和K（1 ≤ N, K ≤ 10⁵）。 - 接下来
N行，每行包含两个整数Hᵢ和Wᵢ（1 ≤ Hᵢ, Wᵢ ≤ 10⁵），表示每块巧克力的尺寸。
输入保证每位小朋友至少能获得一块
1×1的巧克力。
输出描述
输出切出的正方形巧克力最大可能的边长。
输入样例
2 10
6 5
5 6
输出样例
2
c++代码
#include<bits/stdc++.h>
#include<stdio.h>using namespace std;typedef long long ll;int main() {ll N, K, ans = 1, l = 1, r = 100000;scanf("%lld %lld", &N, &K);vector<vector<ll>> arr(N, vector<ll>(2));for (ll i = 0; i < N; i++) scanf("%lld %lld", &arr[i][0], &arr[i][1]);while(r >= l) {ll cnt = 0, mid = (l + r) / 2;for (ll j = 0; j < N; j++) cnt += (arr[j][0] / mid) * (arr[j][1] / mid);if (cnt >= K) ans = max(mid, ans), l = mid + 1;else r = mid - 1;}printf("%d", ans);return 0;
}//by wqs
思路解析
可以证明，如果边长为l的正方形不能分出K块，则变成为l + 1的正方形必定不能分出K块。
这是单调递增的，所以可以用二分枚举正方形的边长。