分巧克力

原題目鏈接

問題描述

兒童節那天有 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塊。
這是單調遞增的，所以可以用二分枚舉正方形的邊長。