当前位置：首页 > news >正文

刚出炉的 Codeforces Round 1100 B 题：一眼像交换，实则一行贪心公式

news 2026/5/25 4:50:18

> 热点来源：
> - Codeforces Round 1100（Spectral::Cup 2026 Round 2）比赛页：<https://codeforces.com/contest/2229>
> - 题目 B `Absolute Cinema`：<https://codeforces.com/contest/2229/problem/B>
> - 比赛预告帖：<https://codeforces.com/blog/entry/153802?locale=en>
> - 官方 Editorial（今日发布）：<https://codeforces.com/blog/entry/153948>

## 摘要

最近 24 小时内，Codeforces 最新一场 `Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2)` 刚刚结束，官方 editorial 也在今天上线。本文选其中很适合写成技术博客的 B 题 `Absolute Cinema`：题面看起来是在每个位置做交换决策，直觉上像是需要分类讨论或 DP，但真正的最优解可以被压缩成一个非常漂亮的贪心公式：

```text
答案 = sum(max(ai, bi)) + max(min(ai, bi))
```

下面我会从问题建模、公式推导、复杂度分析、暴力对拍、可视化解释到完整 Python 代码，把这道题讲透。

## SEO 关键词

Codeforces Round 1100, Absolute Cinema, 贪心算法, 交换决策, Python 竞赛编程, 算法题解, 暴力对拍, 数据可视化

## CSDN 标签建议

`算法` `Python` `贪心算法` `Codeforces` `编程竞赛` `题解` `数据可视化`

## 问题背景

给定两个长度同为 `n` 的正整数数组 `a` 和 `b`。你可以对任意下标 `i` 执行若干次操作：

- 交换 `a[i]` 和 `b[i]`

目标是最大化：

```text
max(a) + sum(b)
```

也就是说，每一对 `(a[i], b[i])` 的两个数最终必须一上一下分到 `a`、`b` 中。你需要决定每个位置是否交换，才能让 `a` 的最大值与 `b` 的总和之和尽可能大。

## 先看直觉：为什么这题容易想复杂

这类题最常见的误区有两个：

1. 以为要“选一个最大值放到 `a`，其余尽量放到 `b`”，但不知道怎样兼顾。
2. 以为每个位置的局部最优会影响全局最大值，所以会往 DP 或排序分类讨论上靠。

其实这题的关键是把“局部贡献”和“唯一的全局最大值贡献”拆开。

## 算法原理

### 第一步：每一对数先标准化

对每个位置 `i`，记：

- `lo[i] = min(a[i], b[i])`
- `hi[i] = max(a[i], b[i])`

那么这一对数无论怎么交换，最终都只是在做两种选择：

- 把 `hi[i]` 放进 `b`，`lo[i]` 放进 `a`
- 或者把 `hi[i]` 放进 `a`，`lo[i]` 放进 `b`

### 第二步：先只看 `sum(b)`

如果完全只追求 `sum(b)` 最大，那么每一对显然都应该把较大的 `hi[i]` 放进 `b`。

于是：

```text
sum(b) 的理论最大值 = sum(hi[i])
```

这一步没有争议，因为每个位置彼此独立。

### 第三步：再看 `max(a)`

如果我们已经把所有较大的数都放进了 `b`，那么 `a` 里每个位置留下的就是 `lo[i]`，此时：

```text
max(a) = max(lo[i])
```

于是马上得到一个可行解：

```text
sum(hi[i]) + max(lo[i])
```

### 第四步：为什么这就是最优解

有人会问：如果我把某个位置的 `hi[i]` 放进 `a`，是不是能让 `max(a)` 更大？

可以，但代价是该位置放进 `b` 的数会从 `hi[i]` 变成 `lo[i]`，也就是：

```text
sum(b) 会损失 hi[i] - lo[i]
```

而 `max(a)` 最多增加到 `hi[i]`。把这两部分加起来看：

- 原方案对这一对的“总效果”相当于：`hi[i]` 在 `sum(b)` 中贡献，外加全局从所有 `lo` 里挑一个最大的做 `max(a)`。
- 如果强行让这对的 `hi[i]` 进 `a`，那 `sum(b)` 少掉 `hi[i] - lo[i]`，但 `max(a)` 最多多出这部分，最终合并起来，本质上仍然只等价于“保留 `hi[i]`，再额外拿到一个 `lo[i]`”。

换句话说，不管你具体怎么交换，最终答案都不可能超过：

```text
sum(max(ai, bi)) + max(min(ai, bi))
```

而这个值又能被“所有较大值进 `b`”的方案直接达到，所以它就是最优解。

## 一句话公式

```python
ans = sum(max(x, y) for x, y in zip(a, b)) + max(min(x, y) for x, y in zip(a, b))
```

## 正确性证明

我们给出一个更紧凑的证明。

设第 `i` 对最终分配后，进入 `b` 的值为 `B_i`，进入 `a` 的值为 `A_i`，显然：

```text
{A_i, B_i} = {lo[i], hi[i]}
```

因此总有：

```text
B_i <= hi[i]
```

从而：

```text
sum(b) = sum(B_i) <= sum(hi[i])
```

另一方面，任意一个进入 `a` 的数都不可能超过对应那对的较小值之外额外白拿收益。因为每一对里如果想让更大的 `hi[i]` 进入 `a`，就必须把 `b` 中同位置的 `hi[i]` 替换成 `lo[i]`，损失正好是 `hi[i] - lo[i]`。

所以，全局最优的结构一定等价于：

1. 尽量让所有位置的较大值贡献给 `sum(b)`。
2. 再从所有较小值 `lo[i]` 中挑一个最大的，作为 `max(a)` 的最佳保底。

于是最优值就是：

```text
sum(hi[i]) + max(lo[i])
```

证毕。

## 复杂度分析

只需要单次线性扫描：

- 时间复杂度：`O(n)`
- 空间复杂度：`O(1)`（如果边读边算）

这也是这道题最漂亮的地方：题面是“逐位交换 + 全局目标”，解法却是一个纯线性贪心。

## 可复现实验

下面给出两部分实验：

1. 用题目样例和自造样例直接运行最优公式。
2. 对小规模随机数据做暴力枚举，对拍验证公式正确。

### 实验思路

对于 `n <= 8` 的情况，可以枚举每个位置是否交换，总共 `2^n` 种方案，然后与线性公式的结果比较。如果两者始终一致，说明我们的推导是可靠的。

## 完整可运行 Python 代码

```python
from __future__ import annotations

from itertools import product
import random
from pathlib import Path

import matplotlib.pyplot as plt

def solve_case(a: list[int], b: list[int]) -> int:
return sum(max(x, y) for x, y in zip(a, b)) + max(min(x, y) for x, y in zip(a, b))

def brute_force(a: list[int], b: list[int]) -> int:
best = -1
n = len(a)
for mask in product([0, 1], repeat=n):
aa: list[int] = []
bb: list[int] = []
for i in range(n):
if mask[i] == 0:
aa.append(a[i])
bb.append(b[i])
else:
aa.append(b[i])
bb.append(a[i])
best = max(best, max(aa) + sum(bb))
return best

def verify_random(trials: int = 200) -> None:
random.seed(20260524)
for _ in range(trials):
n = random.randint(1, 8)
a = [random.randint(1, 15) for _ in range(n)]
b = [random.randint(1, 15) for _ in range(n)]
fast = solve_case(a, b)
slow = brute_force(a, b)
if fast != slow:
raise AssertionError(f"Mismatch: a={a}, b={b}, fast={fast}, slow={slow}")
print(f"Random verification passed: {trials} cases")

def plot_case(a: list[int], b: list[int], out_path: str | Path) -> None:
mins = [min(x, y) for x, y in zip(a, b)]
maxs = [max(x, y) for x, y in zip(a, b)]
pivot = max(mins)

fig, ax = plt.subplots(figsize=(9, 4.8))
xs = list(range(1, len(a) + 1))

for i, (lo, hi) in enumerate(zip(mins, maxs), start=1):
ax.plot([i, i], [lo, hi], color="#1f77b4", linewidth=6, alpha=0.7)
ax.scatter([i, i], [lo, hi], color=["#2ca02c", "#d62728"], s=55, zorder=3)
ax.text(i + 0.05, lo, f"min={lo}", fontsize=9, va="center")
ax.text(i + 0.05, hi, f"max={hi}", fontsize=9, va="center")

ax.axhline(pivot, color="#ff7f0e", linestyle="--", linewidth=2, label=f"max(min_i) = {pivot}")
ax.set_title("Absolute Cinema: each pair contributes max(ai, bi), plus one global max(min(ai, bi))")
ax.set_xlabel("Index")
ax.set_ylabel("Value")
ax.set_xticks(xs)
ax.legend()
ax.grid(alpha=0.25)
fig.tight_layout()
fig.savefig(out_path, dpi=160)
plt.close(fig)

def main() -> None:
sample_a = [2, 3, 6, 7]
sample_b = [1, 4, 5, 8]

ans = solve_case(sample_a, sample_b)
print("Sample case")
print("a =", sample_a)
print("b =", sample_b)
print("answer =", ans)

verify_random()

out_file = Path("absolute_cinema_visualization.png")
plot_case(sample_a, sample_b, out_file)
print(f"Visualization saved to: {out_file.resolve()}")

if __name__ == "__main__":
main()
```

## 如果你要提交到 Codeforces，精简版写法如下

```python
import sys

def solve() -> None:
input = sys.stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = sum(max(x, y) for x, y in zip(a, b)) + max(min(x, y) for x, y in zip(a, b))
print(ans)

if __name__ == "__main__":
solve()
```

## 可视化方案

我推荐把每一对 `(a[i], b[i])` 画成一条竖线段：

- 线段下端是 `min(a[i], b[i])`
- 线段上端是 `max(a[i], b[i])`
- 所有上端求和，对应 `sum(max(ai, bi))`
- 所有下端中的最高点，对应 `max(min(ai, bi))`

这样一张图就能直观看出：

1. 每对数字天然分成“较大值”和“较小值”。
2. `b` 想拿满收益，就尽量吃掉所有较大值。
3. `a` 的最大值只需要从较小值里保住一个最高点。

运行上面的脚本后，会生成：

```text
absolute_cinema_visualization.png
```

## 运行结果解读

以样例：

```text
a = [2, 3, 6, 7]
b = [1, 4, 5, 8]
```

为例：