C++ 代码
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, k;
//C用来存每块巧克力的长和宽
vector<PII> C;
//判断边长为side时,可分得的巧克力数是否>=k
bool check(int side){
int cnt = 0;
for (int i = 0; i < C.size(); ++i)
cnt += (C[i].first / side) * (C[i].second / side);
return cnt >= k;
}
int main()
{
cin >> n >> k;
while (n--){
int h, w;
scanf("%d%d",&h,&w);
C.push_back({h, w});
}
int l = 1, r = N;
while (l < r){
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d",l);
return 0;
}
思路
受昨天y总的每日一题讲解视频的启发,我们可以对巧克力的边长进行二分,然后再将在此边长下可分得的巧克力块数与题目所需要的块数进行比较,最终可得出答案。而这个题目为什么是选用这个模板,而不是 int mid = l + r >> 1那个模板呢?
我的浅显理解是:本题中,我们需要找到巧克力的最大边长,换句话说,我们需要找到一个数,这个数要尽可能的大(我们需要尽可能在区间右侧寻找答案),所以本题的check函数返回值写为cnt >= k,为的就是尽量在区间右侧寻找答案。当mid满足于这个性质时,l的值得到更新(即左区间),我们始终在区间右侧寻找答案。这种操作就类似于不断地对区间的下界进行压缩。(算法初学者,第一次写题解,如有不足之处请见谅)
确实这个区间想了好久 。。唉 还是记板子吧