[CEOI 2017] Sure Bet

题意

可任选四灯泡，每选一个成本 1；最终只点亮 A 或 B 一类。最大化两种结果中较小的净收益。

思路

两类权值分别降序排列。当前较小总收益决定最坏情况，因此下一步若要改善最坏值，应从这一类取最大尚未选择权值。每加入一个灯泡后，用 min(sumA,sumB)-chosen 更新答案；空选择使答案至少为 0。

Python 知识

把四位小数解析成乘 $10000$ 的整数，完全避免浮点比较与输出误差。
zip(*pairs) 分离两类权值，随后各自降序排序。
f-string :04d 固定输出四位小数。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25import sys


def scaled(token):
    whole, _, fraction = token.partition(b".")
    return int(whole) * 10000 + int((fraction + b"0000")[:4])


tokens = iter(sys.stdin.buffer.read().split())
n = int(next(tokens))
first, second = zip(*((scaled(next(tokens)), scaled(next(tokens))) for _ in range(n))) if n else ((), ())
first, second = sorted(first, reverse=True), sorted(second, reverse=True)
i = j = total_first = total_second = chosen = answer = 0

while i < n or j < n:
    if i < n and (j == n or total_first <= total_second):
        total_first += first[i]
        i += 1
    else:
        total_second += second[j]
        j += 1
    chosen += 1
    answer = max(answer, min(total_first, total_second) - chosen * 10000)

print(f"{answer // 10000}.{answer % 10000:04d}")

复杂度

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。

总结

目标由较弱一侧决定，贪心始终用该侧最大剩余收益补平衡。

目录

题意

思路

Python 知识

代码

复杂度

总结