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

算法与贡献¶

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

把家庭看成个人财富¶

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

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

按财富递增进行两次平均

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

对任意当前财富向量，定义 \(\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 对拍，以及反向直方图求和。正式数据还包含差异小于任何普通浮点分辨率的近相等情况。测试与性能说明。