最小化最大值问题 —— Annoyed Coworkers

我报名参加金石计划 1 期挑战 —— 瓜分 10 万奖池，这是我的第 3 篇文章，点击查看活动详情。

题目来自 Open Kattis 上的 Annoyed Coworkers，难度为 3.2（中等）。

作者：Alex Lind 来源：2019 Virginia Tech High School Programming Contest (Problem H) 许可：

文章内容参考比赛主办方的题解大纲。

题目

又是在办公室的一天。你是一个不会独自完成任何工作的高管。相反，你会去找你的同事寻求“帮助”，伺机让他们完成所有的工作。

你很清楚知道，忙帮得越多，人就越恼火。在一开始时，同事对你的怒气值为 aaa。当你想向他们寻求帮助时，他们的怒气程度会以恒定 ddd 的数量增加。

你希望在同事的“帮助”下完成 hhh 个任务项目，但你需要注意不要过度地惹恼任意一个同事。

那么，最好的策略是什么？

输入

第一行包含两个整数 hhh 和 ccc，其中 hhh（1≤h≤1051 \le h \le 10^51≤h≤105）是你需要寻求帮助的次数，ccc（1≤c≤1051 \le c \le 10^51≤c≤105）表示的是你的同事数量。

接下来 ccc 行中的每一行包含两个正整数 aaa 和 ddd，代表每个同事对你的初始怒气值，和每次寻求帮助后的怒气增量 ddd（1≤a,d≤1091 \le a, d \le 10^91≤a,d≤109）。

输出

输出一个数字，即同事对你的最大怒气值，前提是你应该最大限度地降低这个值。

例子

例 1

4 4
1 2
2 3
3 4
4 5

7

解释： 你有 444 个同事和 444 个项目需要“帮忙”。他们的初始怒气值为 a1=1a_1 = 1a1​=1，a2=2a_2 = 2a2​=2，a3=3a_3 = 3a3​=3，a4=4a_4 = 4a4​=4，怒气增量为 d1=2d_1 = 2d1​=2，d2=3d_2 = 3d2​=3，d3=4d_3 = 4d3​=4，d4=5d_4 = 5d4​=5。

其中一种最佳的解决方案是：向同事 111 请求帮忙两次，向同事 222 请求一次，向同事 333 请求一次。最终怒气值为：

对你最恼火的同事是同事 333，怒气值为 777。

又或者，你可以向同事 111 请求帮忙三次，向同事 222 请求一次。最终怒气值为：

两种策略都产生相同的结果。

例 2

3 2
1 1000
1000 1

1002

例 3

5 2
1 1
2 2

5

题目要求

输入：hhh，ccc，a1,a2,…,aca_1, a_2, \ldots, a_ca1​,a2​,…,ac​ 和 d1,d2,…,dcd_1, d_2, \ldots,d_cd1​,d2​,…,dc​ 输出：最小化 a1+n1⋅d1,a2+n2⋅d2,…,ac+nc⋅dca_1 + n_1 \cdot d_1, a_2 + n_2 \cdot d_2, \ldots, a_c + n_c \cdot d_ca1​+n1​⋅d1​,a2​+n2​⋅d2​,…,ac​+nc​⋅dc​ 的最大值 条件：∑i=1cni=h\displaystyle\sum^{c}_{i=1}{n_i} = hi=1∑c​ni​=h（ni≥0n_i \ge 0ni​≥0）

解题思路

对于每次请求，我们每轮都应该选择请求后怒气值最小的那位同事。也就是说，其他的东西，像是初始值和增量什么的，都不是关键。

因此，我们需要频繁地查找最小值，但每次修改怒气值后都排序一遍显然是会超时的。

这时最小堆就派上用场了。

最小堆满足下列性质：

• 堆中某个结点的值总是不小于其父结点的值；
• 堆总是一棵完全二叉树。

根据这一性质，最小堆的根节点总是最小值。

在 Python 中，heapq 库提供了相关的算法。heapify 函数能将数组转换成堆，而 heappush 和 heappop 则分别对应插入和删除操作。更多详情请看这里。

注：堆的删除操作只能删除根节点。

时间复杂度：O(hlog⁡c)O(h \log{c})O(hlogc) 空间复杂度：O(c)O(c)O(c)

代码

from heapq import heapify, heappop, heappush

# 请求数量，同事数量
h, c = map(int, input().split())
# 每个同事的 [怒气值，增量]
ai = [list(map(int, input().split())) for _ in range(c)]

# 预测请求后的怒气值
# `ai` 不需要了，`predicted` 可以直接覆盖它（这里就不这么做了）
predicted = [(a + d, d) for a, d in ai]
# 构建堆结构
heapify(predicted)

# 对于每个请求
for _ in range(h):
    # 获取 `predicted` 中最小的值（也就是堆的根节点）
    level, d = heappop(predicted)
    
    # 请求同事 `idx` 的帮助
    # 预测下一轮的请求后的怒气值
    
    # `predicted` 不需要从新计算
    # 只有一个同事的当前怒气值更改了，再为该同事的怒气值加个 `d` 即可
    heappush(predicted, (level + d, d))

# 请求完毕
# 把 `predicted` 里的每个值回退一轮（减去 `d`），获得当前每个同事的怒气值
# 输出同事中的怒气最大值
print(max(level - d for level, d in predicted))

总结

1. 对于最小化最大值/最大化最小值的问题，贪心算法可能适用。
2. 需要多次查询列表中的最大值/最小值时，应考虑使用堆。
3. 柿子挑软的捏。

相关知识点：贪心算法、堆（优先队列）