思路:
小巧克力边长 a 一定在 1 – 100000 之间
答案即为:在 1 – 100000 之间找到一个最大的数,使得所有的 (w[i]/a) * (h[i]/a) 之和大于要求的数量 k。
使用二分法找到 a 的最大取值即为答案。
//cpp
#include <iostream>
using namespace std;
int const N = 100010;
int w[N], h[N];//存储长、宽
int n, k;
bool chack(int a)
{
int num = 0;//记录分成长度为 a 的巧克力数量
for (int i = 0; i < n; i++)
{
num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量
if (num >= k) return true;//大于要求数量,返回真
}
return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> h[i] >> w[i];
int l = 1, r = 1e5;//小巧克力数量边长一定在 1 -- 100000 之间
while (l < r)//二分小巧克力边长范围,找到符合要求的最大值
{
int mid = l + (r - l + 1 >> 1);//因为l = mid ,所以 mid 取 l + r + 1 >> 1,为了防止加和越界,改写成 l + (r - l + 1 >> 1)
if (chack(mid)) l = mid;
else r = mid - 1;
}
cout << r;
}
有问题直接评论即可。
如果对你有帮助,求个点赞~
我的问题是应该是check而不是chack啊……哈哈哈哈
可以意会,不可言传
二分结束的时候,l = r , 此时mid 还是上一次的mid ,没更新:
当mid=8时不成立,更新l=r=mid-1=7;
有没有说改变check然后用第一个模板来写的大佬,求教
运用函数,把谁的值赋值给a了?ture和flase分别对应的是if还有else吗
(w[i] / a) * (h[i] / a)那里为什么不能写成(w[i] * h[i]) / (a * a) 啊??
两个数相乘,可能溢出
不是溢出的问题,例如巧克力是1*100,但a是2,前者确实是不能分的,后者就错了
在check函数里 在for循环里面不是就两遍吗 怎么计算到是否有k个呀
每个巧克力能分的块数总和和k比较
前面式子的意思是横着能分三块, 竖着能分两块, 总共能分3*2=6块
后面式子的意思是巧克力总块数 / 最大正方形块数, 第二个式子成立, 第一个式子不一定成立, 题意要的是第一个式子
感谢分享,收获颇大
我人傻了,除法用成取余,调试了半天
大佬,可以帮帮菜鸡康康吗?
bool check(int a)
{
}
这题int sum=0 写到最上面为什么不行
如果sum是全局变量,不会重新刷新为0,而会一直叠加
还是不太理解这里的mid加和越界, mid=l+r+1>>1 也能过吧
不行 数据多了机会TLE
为什么num>=k,l=mid,而不是r=mid,我觉得>=k时,最大边长在【1,mid】啊
我是这样想的,他切的数量多了,每个小巧克力边长变大的话,才可以使num变小;mid存的是每个小巧克力边长
嗯嗯 谢谢!我后面听别借教室的课有了点理解。我现在理解的是num和边长成反比,在num>=k时,num对应的边长mid<=最大边长,所以最大边长在mid右边,就是取l=mid。我之前理解错,好像是因为对最大边长和mid弄混了。我觉得mid是当前num对应的边长,而k对应的最大边长x是二分求得的,通过不断改变区间来得到新的mid,求x。
请问这里为什么l为什么更新到mid而不是mid+1
我的理解是,这里二分枚举的是答案,当check满足时,答案可能在mid,或者的后面
我的理解是:根据y总的两个模板,如果if(true)找的是左边区间的右端点 那么就是l=mid的模板 反之r=mid
在这一题中if(true) 的情况是:正方形巧克力边长越小则一定true 所以是左边区间的右端点
请问这个地方是怎么出来的哇😭
num += (w[i] / a) * (h[i] / a);//每一大块可以分成的边长为 a 的巧克力数量
我理解的是,w[i] * h[i]是大巧克力的面积,a * a是分出去的小巧克力的面积,两者相除就是能分出去的数量
这下想通了 谢谢!
其实这样理解是错误的。因为分出去的小巧克力是正方形的,所以小巧克力对大巧克力的长度和宽度是由要求的。
哦哦,那应该怎么想呀
w[i] h[i]是矩形的长和宽,而(w[i] / a) *(h[i] / a)就是分别满足长宽的小巧克力的个数。我们二分的就是找到一个a让这个数为满足条件的最小值
感觉可以稍微优化一点点,把右边界设置成最大的边长就行
其实没有必要,因为二分的复杂度是$O(logn)$,在这个玩意面前最大边界大一两个数量级变化都不明显
# 不知道为啥,我优化之后过不了
我也是(大哭)
为什么l+r要+1啊,我没加1的时候是死循环
如果不加1,会取到l本身,死循环
很棒,思路简洁明了
为什么是 num += 啊,没看懂,可以讲解一下吗
不能写 num = 吗
num是记录可以取得最大边长a的巧克力块数的,而题目给的例子是有总块数的,如果是num =就不符合题意了也不对了
h/a *w/a就是求可以划成几块a * a几的巧克力的公式,(个人理解)
好的,感谢
我这个二分为什么不对呢,只不过思路是反着来的 ,求指点
我这样子写就是对的
像上面那样写就是错的
就是二分查的时候不一样,但是为什么啊,上面的二分哪里不对呢?
正确的代码如下
check 成功,r = mid 往小的找 答案是对的,不符合题目找大的要求
同问
可以举个例子嘛
同问
我有一点不明白,代码从哪里能保证巧克力保证的性质呢?求大佬告知
就是是正方形,而且相同
哦,撤回,我没认真看题
感觉比用pair舒服