解题思路:一块巧克力能分划分的最大块数就是用两个边长除以要分的边长,向下取整再相乘,比如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语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:667 |
【回文数(二)】 (C语言代码)浏览:855 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:857 |
淘淘的名单 (C语言代码)浏览:1104 |
用筛法求之N内的素数。 (C语言代码)浏览:807 |
剪刀石头布 (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:517 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:401 |
敲七 (C++代码)浏览:1056 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:817 |