1885: 蓝桥杯2017年第八届真题-分巧克力(3.15)

解题思路:在这个网站无法ac,在官网ac了,思路有两个

1.暴力枚举每一个输入的巧克力的可能分割方案的数目,直接统计总和,找到总和小于k的那一个前面的一个即为最大边长.官网得分75,两个测试点超时
2.基于方法一我们来考虑一下,我们在方法一中记录了所有边长能得到的子巧克力数目,有没有办法能减少我们枚举的边长呢?换言之,我们希望每当我们尝试一个边长就能排除一定数量的边长,而二分查找就具有这样的性质.具体:二分枚举可能的最大边长,当求出来的子巧克力的数目小于k时说明,边长过大,应该减小边长.若大于等于k说明边长较小但可能是最大边长,增大边长并记录一下最后一个大于等于k的边长(因为求的是最大),官网得分100
注意事项:

参考代码:

#思路一实现
import time#测试性能,提交时删除

# 方法一:遍历所有巧克力,并把能分割的边长的子巧克力数目统计,找到第一个边长数目小于人数的
start = time.clock()
n, k = map(int, input().strip().split())
cuts = [0 for _ in range(100001)]
for i in range(n):
    r, c = map(int, input().strip().split())
    small = min(r, c)
    j = 1
    while j <= small:
        cuts[j] += ((r // j) * (c // j))
        j += 1
for x in range(1, 100001):
    if cuts[x] < k:
        print(x - 1)
        break
end = time.clock()
print(end - start)

#思路二实现
n, k = map(int, input().strip().split())
chocolates = []
for i in range(n):
    chocolates.append(tuple(map(int, input().strip().split())))

left, right = 1, 100000
cut = 1
while left <= right:
    mid = (left + right) // 2
    sum_up = 0
    for j in range(len(chocolates)):
        sum_up += (chocolates[j][0] // mid) * (chocolates[j][1] // mid)
    if sum_up >= k:
        left = mid + 1
        cut = mid
    else:
        right = mid - 1
print(cut)