（贪心）数学证明 | [P1080] 国王游戏(简化版)
[P1080] 国王游戏(简化版)
https://www.nowcoder.com/practice/145c3426577f40f8b2b5e51ca6f61523
题目分析
我们需要安排 n 个大臣的顺序，使得获得最多金币的大臣所获得的金币数尽可能少。
金币计算公式
对于第 i 个大臣，其金币数为：
其中 表示国王的左右手数字。
贪心策略证明
我们需要找到一种排序方式，使得所有大臣中金币数的最大值最小化。
按 升序排列是最优策略。
数学证明
考虑相邻两个大臣 i 和 j，且 ，设
交换前（顺序：）:
- 大臣 i 的金币：
- 大臣 j 的金币：
交换后（顺序：j→i）:
- 大臣 j 的金币：
- 大臣 i 的金币：
由于 ，可得：
因此交换前的最大金币数为 ，交换后的最大金币数为
，且：
所以交换后最大值不会更大，按 升序排列是最优策略。
代码实现
import sys
def main():
input = sys.stdin.readline
n = int(input())
a0, b0 = map(int, input().split())
arr = [tuple(map(int, input().split())) for _ in range(n)]
# 按a_i*b_i升序排列
arr.sort(key=lambda x: x[0]*x[1])
max_coins = 0
prefix = a0 # 记录前缀乘积
# 找出金币最多的大臣的金币数
for a, b in arr:
coins = prefix // b
if coins > max_coins:
max_coins = coins
prefix *= a
print(max_coins)
if __name__ == "__main__":
main()
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
查看5道真题和解析