# 简单合并

## 解法与署名

出题人解法：各序列统一为不降顺序，用堆维护每个未空序列的首元素。Codex（GPT-6）整理标准 C++17 实现与重复值、零次操作的边界。程序：[std.cpp](std.cpp)。

另提供[胜者树](solution-alternative-tournament.zh.md)与[程序](alternative-tournament.cpp)，用固定叶子和逐层取最小值维护同一个候选集合。两者同阶；堆仍为首选，胜者树提供不同的更新结构，不把同阶替代称为渐进优化。

## 首元素足以代表一个序列

设总元素数为 $S=\sum s_i$ .若一个序列首元素大于末元素，将其翻转；否则它已经不降，首尾相等时由单调性可知整个序列相等。

每个未空序列的最小剩余元素位于当前首位置。因此所有剩余元素的最小值，一定在这些首元素中。

把每个首元素及其所属序列编号放入最小堆。每次弹出堆顶并输出，只向前移动这个序列的指针；它仍非空时，把新的首元素加入堆。

## 正确性

初始堆恰好包含每个未空序列的首元素。假设操作前保持该不变量，堆顶就是全局最小值。删除它只改变一个序列的首元素，补入这个序列的新首元素便恢复不变量。由操作次数归纳，全部输出正确。

重复值按出现次数分别保留。序列编号只用于相等值之间稳定比较，不改变输出的数值。$m=0$ 时完成读入后不弹堆；$m=S$ 时恰好删光全部元素。

## 复杂度

读入和翻转共 $O(S)$ .当前程序逐个插入初始首元素，堆操作共 $O((k+m)\log(k+1))$ ，总时间 $O(S+(k+m)\log(k+1))$ .存储全部输入和堆需要 $O(S+k)$ 空间。

胜者树初始化为 $O(k)$ ，每次替换一个叶子为 $O(\log(k+1))$ ，总时间 $O(S+k+m\log(k+1))$ ，空间同为 $O(S+k)$ .由于 $k\le S$ ，两者总时间阶相同；具体耗时以实测为准。

## 验证与运行

用展平全部元素后排序的独立模型对拍，覆盖不同单调方向、重复值、零次删除及删光全部元素。

每题的 `tests/plan.json` 包含十份输入的固定种子和目的。编译程序后，可运行：

```text
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
```

省略 `--std` 只生成输入，`--case 01` 选择单份输入。独立验证脚本见 [check_r15.py](../../../tools/check_r15.py)。五轮交替计时与内存记录见[测量数据](../../../docs/benchmark-R15.json)，环境说明见[评测环境与性能](../../../docs/评测环境与性能.md)。有限测试与具体程序的计时不代替上面的证明，也不保证所有同阶实现都能在同一时限内通过。

## 实测结果

| 程序 | 最慢用例中位时间 | 峰值工作集 |
| --- | ---: | ---: |
| 标程 | 0.176663 秒 | 9.00 MiB |
| 补充程序 | 0.159656 秒 | 9.01 MiB |

参考时限为 0.5 秒。十份已测正式输入上，两份程序结果一致，均在该时限内完成。上述内存是包含进程开销的峰值工作集，时间与内存的最大值可能来自不同输入。