解题思路:一块巧克力能分划分的最大块数就是用两个边长除以要分的边长,向下取整再相乘,比如5*6分为2*2的,就是(5//2)*(6//2)=6块,随着边长取得越大,能分的快数也就越少,这里就有了明显的单调性,然后我们就可以做一个检查函数,用于检查是否当前所取的边长能够满足块数需求,利用向右逼近的二分进行检索即可,两个边界分别取1和1e5,因为这里每个人最少有一个1*1的巧克力,最大边长肯定不超过hi或wi最大值,超过的话一个也分不了
注意事项:整数二分,向右逼近的取法别忘了mid每一次向上取整
参考代码:
def check(i):
res=0
for j in range(n):
res+=(hi[j]//i)*(wi[j]//i)
if res>=k:
return 1
return 0
n,k=map(int,input().split())
hi=[]
wi=[]
for i in range(n):
h,w=map(int,input().split())
hi.append(h)
wi.append(w)
l=1
r=10**5
while l<r:
mid=(l+r)//2+1
if check(mid):
l=mid
else:
r=mid-1
print(l)
0.0分
1 人评分
母牛的故事 (C语言代码)浏览:1716 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:705 |
求圆的面积 (C语言代码)浏览:1271 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:638 |
【亲和数】 (C语言代码)浏览:503 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:605 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:484 |
WU-蓝桥杯算法提高VIP-企业奖金发放 (C++代码)浏览:1176 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:560 |
母牛的故事 (C语言代码)浏览:945 |