# 编辑城镇与模拟币：题解

## 算法与贡献

Codex（GPT-6）给出顺序平均的最优性证明、七项统计公式，以及避免浮点误判的逆向整数阈值算法。[std.cpp](std.cpp)适用于题面规定的单人目标家庭和初始人数上限20.

## 把家庭看成个人财富

把一个家庭拆成单人家庭，每人恰好得到初始人均财富。此后合并一组人再拆开，等价于把他们的个人财富全部替换成均值。任何一次搬家也可按这种平均操作描述，因此可以用个人财富向量分析。

记目标初始财富为 $a=m_1$ ，其他人的初始财富为 $v$ . 最优策略是：只取 $v>a$ 的人，按 $v$ 非降顺序，依次与目标组成两人家庭，再拆开。目标每次从 $x$ 变为 $(x+v)/2$ . 每个人至多使用一次。

![按财富递增进行两次平均](assets/example.svg)

## 为什么任意编辑不能更好

对任意当前财富向量，定义 $\Phi$ 为上述排序策略得到的目标财富。先证明它是在“不重复使用外部个人”的所有顺序平均方案中的最大值。相邻交换时，先用较小的 $u$ 再用较大的 $v$ ，比反序多得 $(v-u)/4$ ；后续平均只会把这个差乘以正数。因此可以排序。排好序后，不大于起始目标财富的人可删除；漏掉的更富者按顺序插入会增加结果。

下面证明任何两人平均都不会增大 $\Phi$ ：

- 两人都不是目标：$\Phi$ 是若干个线性函数（各不重复顺序）的最大值，所以关于外部财富是凸函数；它还对外部人员置换对称。把两个坐标平均是原向量和交换后向量的平均，凸性给出不增。
- 包含目标且对方更富：平均后该人的财富等于新的目标财富，后续排序策略不再使用他。因此整个过程仍是平均前某条不重复使用外部人的序列，不超过平均前的 $\Phi$ .
- 包含目标且对方不更富：平均后目标变穷，对方与新目标相等，也不会再次使用。删去该人后，$\Phi$ 关于目标财富单调，故仍不增。

任意多人平均可以由该组内循环的两人平均逼近；组内平方偏差不断缩小并趋于零。$\Phi$ 是有限个线性函数的最大值，因而连续，所以多人平均也不会增大它。初始 $\Phi$ 因此是所有允许编辑的上界，而排序策略用有限步达到它。这就证明了最优值 $A$ .

## 不展开人数

同一个初始家庭的 $p$ 个人都有相同的财富 $v=m/p$ . 连续处理这一批后：

$$x'=v+(x-v)2^{-p}.$$

按分数 $m/p$ 排序，使用交叉乘法比较。每个家庭只做一次模更新；预处理 $1,\ldots,20$ 的模逆和 $2^{-p}$ 即可。跳过 $v\le a$ 的家庭。排序后目标始终小于尚待使用者的财富，故每个富人都会使它严格增加。

## 最小外部财富与人均差距

设外部人数为 $Q$ ，最终外部总财富为 $O=\sum_i m_i-A$ . 若 $Q=0$ ，直接输出题面规定的特例。否则令外部初始人均财富最小值为 $v_{\min}$ ，则达到最优时，外部个人财富的最小可能值为

$$b=\begin{cases}v_{\min},&v_{\min}\le a,\\(a+v_{\min})/2,&v_{\min}>a.\end{cases}$$

第一种情况下，平均不能降低全局最小值，而排序策略不动这个人。第二种情况下，目标第一次与其他人发生有效平均时，参与的其他人财富至少为 $v_{\min}$ ，平均结果至少为 $(a+v_{\min})/2$ ；此后所有人的财富都不小于此值。排序策略第一步正好达到这个界。

任何最优方案中，外部家庭的人均财富都不能大于 $A$ ，否则取出一名该家庭成员，与目标平均后分开，会进一步提高目标财富，矛盾。于是最大人均差距为 $A-b$ ，排序策略后把最穷者单独成家即可达到。

## 家庭财富差距

当 $Q=1$ 时只能是两个单人家庭，差距为 $|A-O|$ . 当 $Q\ge2$ 时，按最富和最穷家庭是否为目标分类，得到

$$G=\max(A-b,\ O-2b,\ O-A).$$

若目标最富，差距不超过 $A-b$ ；若目标最穷，外部最富家庭财富不超过 $O$ ；若两个极端都是外部家庭，最穷家庭至少有财富 $b$ ，最富家庭至多有 $O-b$ . 把最穷外部个人单独成家、其他外部人员合成一家，可同时给前两个候选值提供下界；把全部外部人员合成一家可达到第三个候选值。因此最大值可实现。

若存在初始更富者，最后一名被使用者的最终财富也为 $A$ . 所以 $Q\ge2$ 时有 $O\ge A+b$ ，公式可简化为

$$G=O-\min(A,2b).$$

若没有更富者，则 $A=a$ 是整数，直接把三个候选值通分到 $v_{\min}$ 的分母后比较。

## 四个判断

排序策略结束后，所有外部个人都不比目标富，故第4和第6项始终为1.

由于目标只有一个人，两项严格判断都等价于 $AQ>O$ . 必要性来自总财富：若每个外部家庭总财富都小于 $A$ ，则其人均财富也小于 $A$ ，外部总均值也必须小于 $A$ . 充分性是把全部外部人员合并后拆成单人家庭，使每人的财富都为 $O/Q<A$ .

无需对巨大有理数作比较：存在更富者时，$Q=1$ 最终两人相等，$Q\ge2$ 时除最后一位使用者之外至少有一人严格较穷，故严格判断为1；没有更富者时，判断是否存在初始严格较穷者即可。

## 精确比较 $A$ 与 $2b$

模值不能比较大小，浮点数也可能把极小差异舍入成相等。取

$$D=2\operatorname{lcm}(1,2,\ldots,20)=465585120.$$

所有初始人均值和 $b$ 乘以 $D$ 都是整数，但 $A$ 仍可能有巨大的二进制分母。我们不计算它，而是反向传播达到阈值所需的条件。

设当前阈值为 $T$ 、一批富人的比例尺财富为 $V$ ，则

$$x'=V+(x-V)2^{-p}\ge T\quad\Longleftrightarrow\quad x\ge V+2^p(T-V).$$

初始阈值为 $2bD$ . 逆序处理富人家庭：

- 若 $T\le aD$ ，必定能达到，立即返回真。
- 若 $T\ge V$ ，这一批结束后财富严格小于 $V$ ，立即返回假。
- 否则令 $\delta=V-T>0$ . 若 $2^p\delta>V-aD$ ，反向阈值已低于初值，返回真；用 $\delta>\lfloor(V-aD)/2^p\rfloor$ 先比较，避免乘法溢出。
- 其余情况安全计算新阈值 $V-2^p\delta$ ，继续逆推。

这样所有中间阈值都是有界整数，保持等价条件，精确相等也能正确处理。最大初始比例尺财富不到 $4.66\times10^{14}$ ；没有更富者时的通分分子不超过 $2\times10^{13}$ ，均在64位范围内。模乘法的两因子均小于 $P$ ，也不会溢出有符号64位整数。

## 复杂度与检验

时间 $O(n\log n)$ ，空间 $O(n)$ ，不依赖展开后的总人数。题目所求极值只用初始人数分母和2的幂，所以其模逆存在；不对编辑过程中所有可能的分母作多余假设。

独立验证包含任意子集平均对势函数的检查、外部家庭分区穷举、展开人口的精确 Fraction 对拍，以及反向直方图求和。正式数据还包含差异小于任何普通浮点分辨率的近相等情况。[测试与性能说明](tests/README.md)。