题目描述
思路
求最大边长，一开始我看这个题的第一眼，求最值？贪心？dfs？dp？但这些感觉都没有适用的
看了题解，才发现可以二分！二分的使用条件就是求某一范围的某个数，这个范围内的数要有单调性！这个题正好
代码
因为巧克力的大小是固定的，边长越大，则能分割出来的巧克力块越小，要求最大可能边长
求最大边长，即求小于等于，即求右边界，即mid = l + r + 1 >> 1;
#include<bits/stdc++.h>using namespace std;const int N = 1e5+10;
int h[N],w[N];int n, k;
bool check(int x)
{int ans = 0;for(int i = 1; i <= n; i++){ans +=h[i] / x *( w[i]/x); //取个最小值，表示当前这块巧克力所能分的小朋友}if(ans >= k) //说明可以分return true;return false; //不可以分
}
int main()
{//分巧克力找的是小于等于的，因为左边的都满足，所以套右边界的板子cin >> n>>k;//最大的边长就是巧克力的最小边长int r = 0x3f3f3f3f;for(int i = 1; i <= n; i++){cin >> h[i]>>w[i];r = min(min(h[i],w[i]) ,r);}puts("ok"); int l = 1;//这个数组是单调递增的,边长数//最大边长while(l < r){int mid = l + r + 1 >>1;if(check(mid)){//当前的满足l = mid; //因为条件是有等于的}elser = mid - 1;}cout<<l <<endl;return 0;
}
总结
这个题启发我：
二分也可以用来求最值！但要满足单调性!