蓝桥杯真题：分巧克力

蓝桥杯 2017 年省赛真题《分巧克力》的 Python 解法。

蓝桥杯 2017 年省赛真题：分巧克力。

题目链接：https://www.lanqiao.cn/problems/99/learning/（需要登录）。

题目大意

将 $N$ 块大小为 $H_i\times W_i$ 的巧克力切出部分分给 $K$ 人，要求分给 $K$ 人的巧克力大小相等且都为边长是整数的正方形。求可能分法中每人巧克力的边长最大值（测试点保证答案不小于 $1$）。

数据范围

$1\leq N,K,H_i,W_i\leq10^5$。

运行限制

• 时间限制：2s。

分析

Python

注意到数据范围上限都是 $10^5$，可以猜测本题一解的时间复杂度为 $O(N\log N)$，继而联想到二分法。

那本题如何绕到二分上呢？先看选定不同的边长对分巧克力过程的影响。从题目中可知若记切出的巧克力的边长为 $a$，能切出 $b$ 块满足题设条件的巧克力，那么所有边长小于 $a$ 的切法均能切出不少于 $b$ 块巧克力。换言之，若将考察范围内的边长排成一个序列，一定存在某个元素 $a_\mathrm{ans}$，使得在它之前的边长以及它本身都是满足题设条件的分法，而在它之后的边长都不满足——这就说明这个序列可以视作有序的，其元素值仅能被划分到“满足条件的”和“不满足条件的”两类中，而我们则需要找到这两类元素的“分界线”——这正是二分法的一种典型应用。

此外，我们发现，对于给定的边长 $a$ 和大小为 $H_i\times W_i$ 的巧克力，如果尽可能一块紧挨着一块切分，可以达到最大份数，具体数值为 $\left\lfloor\dfrac{H_i}{a}\right\rfloor\left\lfloor\dfrac{W_i}{a}\right\rfloor$。这也说明判断某个边长是否满足题设条件的时间复杂度为 $O(N)$。结合上述二分的描述过程，此解法的时间复杂度恰好为 $O(N\log N)$。

完整代码

Python

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
h, w = [None] * n, [None] * n
for i in range(n):
    h[i], w[i] = map(int, sys.stdin.readline().rstrip().split())

# 考察范围的上限为所有巧克力中长和宽的最大值
maxh, maxw = max(h), max(w)
maxhw = max(maxh, maxw)
# f[i] 为某个边长 i 是否满足题设条件
f = [None] * (maxhw + 1)

# 参考：Python 安装目录下 Lib/bisect.py
# 注意：在更高 Python 版本中，内置模块 bisect 支持在二分查找和排序中加入 `key` 参数，若将判断边长是否符合条件的过程写成函数，则可以
# 直接代入 `bisect.bisect_left()`，且该内置函数经过 C 语言优化，运行速度更快。
lo, hi = 1, maxhw + 1
while lo < hi:
    mid = (lo + hi) // 2
    # 若 `f[mid]` 未被计算出，则开始计算
    if f[mid] is None:
        s = 0  # 可分出的巧克力块数
        f[mid] = False
        for i in range(n):
            s += (h[i] // mid) * (w[i] // mid)
            # 本题无需计算出分出巧克力的具体块数，则在判断出其已经超过 `k` 时直接跳出
            if s >= k:
                f[mid] = True
                break
    if f[mid] == True:
        lo = mid + 1
    else:
        hi = mid

# `lo` 即为 `bisect.bisect_left()` 的返回值，其为不符合题设条件的边长最小值
print(lo - 1)