蓝桥杯真题:分巧克力

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

完整格式链接:蓝桥杯真题:分巧克力 - LittleYe233's Blog

蓝桥杯 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)

2 Likes