这个题目属于整数二分和上一次的题目类似剪绳子
浮点数二分相对于整数二分来说比较简单,因为浮点二分如果套用模板的话就只有一个,有思路基本上可以直接写。
但是整数二分就需要考虑一下边界问题,因为他有两个模板。
模板1
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
模板2
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid) l = mid;
else r = mid - 1;
}
对这个题目来说由于是从长方形,要分成正方形。
设长方形的长和宽为:$X$和$Y$。
设正方形的长和宽为:$a$。
由公式可知:可分为正方形数量为:$(X \div a) \times (Y \div a)$
如果$a$很大那么分成巧克力的数量就小,因此该题通过二分寻找为正方形边长为从大到小因此我们采用下面这个模板2
对于模板的理解纯属个人见解,请大佬们扶正~
代码详解
#include <cstdio>
#include <utility>
using namespace std;
/**
* @param N 表示有多少块巧克力
* @param K 表示有多少个小朋友
* @param H 表示巧克力的长
* @param W 表示巧克力的宽
*/
const int M = 100010;
int N, K;
int H, W;
pair<int, int> arr[M];
/**该函数用来判断,可以分成的巧克力的数量是否大于或小于小朋友的数量
* bool check(int k)
* @param k 表示当前可能的边长
* @return true
*/
bool check(int k) {
int res = 0;
for (int i = 0; i < N; ++ i) {
res += (arr[i].first / k) * (arr[i].second / k);
if (res >= K) return true;
}
return false;
}
int main() {
scanf("%d%d", &N, &K);
// 用pair来存巧克力的长和宽
for (int i = 0; i < N; ++ i) {
scanf("%d%d", &H, &W);
arr[i] = make_pair(H, W);
}
// 对将要分成巧克力的边长进行二分
int l = 1, r = 1e5;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d", r);
return 0;
}
python解法
# 由于input读取之后返回的是字符串,所以需要通过这种方式读入,split是用来分隔的
N, K = map(int, input().split())
arr = []
def check(k):
res = 0
# 对arr数组进行循环,取出里面的两个值
for W, H in arr:
res += (W // k) * (H // k)
if res >= K:
return True
return False
if __name__ == "__main__":
# 这种循环的写法是方便读入数据
for _ in range(N):
w, h = map(int, input().split())
arr.append([w, h])
left = 0
right = 100000
while left < right:
mid = (left + right + 1) >> 1
if check(mid):
left = mid
else:
right = mid - 1
print(right)