UVa 12259 Fair Division：最大余数法实现整数公平分配与C++避坑指南

做 OJ 题这么多年，经常会碰到一类题：题面说得挺热闹，抽成数学模型之后反而清爽，UVa 12259 Fair Division 就是典型。这题的核心不是“把奖金按比例分一下”这么简单，而是要在整数约束下做到“尽可能公平”。如果不把题面里的几个隐藏约束读透，第一版代码几乎必错。这篇记录我从题意理解、算法推导到最终 AC 的完整过程，附带可以照抄的 C++ 实现和几个只有实际提交过才会遇到的坑。

先交代一句这题在解决什么问题：有一群人合伙买了一张彩票，每个人掏了不同金额的钱，现在中奖金额是一笔整数。规则是每个人都至少能拿到 1 元，且所有奖金必须恰好分完，不能有剩余，也不能透支。要求是，分到手的钱要尽量贴近“按出资比例应得的钱”。

乍一看很普通，但一旦动手写，就会发现“整数”两个字把所有舒服的公式都堵死了。下面我把这题拆开讲。

1. “公平”这个词，到底要怎么翻译成代码

1.1 把题意抽成数学模型

我拿到题之后习惯先不急着敲代码，而是把题面里所有条件列成一条条数学约束，这样后面写在代码里才不容易漏。

UVa 12259 给我的第一印象是：假设有 n 个人，第 i 个人投入了 p[i] 元，总投入 T = sum(p[i])。中奖金额为 M。需要输出长度为 n 的整数序列 b[i]，满足：

• b[i] >= 1，也就是每个人至少拿到 1 元；
• sum(b[i]) = M，奖金必须全部分完；
• b[i] 要尽可能和 p[i] * M / T 成正比。

这个“尽可能”就是整道题最暧昧的地方。因为如果允许分配金额是小数，b[i] = p[i] * M / T 直接就是答案，代码三行写完，题目没有任何存在感。

所以，“公平”必须在一个整数分配的框架里去定义。最自然的标准是：每个人应得的理想金额是 e[i] = p[i] * M / T，由于取整，每个人最终拿到的金额应该落在 floor(e[i]) 或 ceil(e[i]) 之间，不应该出现有人比 ceil(e[i]) 还多、同时另一个人连 floor(e[i]) 都拿不到的情况。

这个定义看起来是废话，但它其实给了后面算法一个非常清晰的验收标准。你写出来的任何解法，都逃不过这个检查：把最终分配结果和 floor/ceil 比对一下，就知道有没有偏离公平。

1.2 保底条款改变了分配顺序

题目里“每个人都至少拿 1 元”这个条件特别容易让人忽略。第一眼看去，它只是一个人为设定的下限，似乎处理方式就是“按比例分完后，如果有人分到 0，就把他调成 1，再从别人那里扣回来”。

我一开始就是这么做的，样例也过了，但交上去 WA。问题出在，这是错误的逻辑顺序。

保底条款意味着 M 这笔钱并不是完全按比例分配的，其中 n 元已经提前按人头均分掉了。真正需要按比例分配的，是 M - n 那一部分。正确的建模是这样的：

• 先把 n 元平摊给每个人，每人保底 1；
• 剩余金额 C = M - n；
• 把 C 按出资比例 p[i] 分给每个人。

为什么必须这样拆分？因为当保底金额存在时，你如果直接对 M 做比例分配，然后给 0 元的人补到 1，会导致总金额超过 M，必须再从某个人的份额里扣钱。而扣谁的钱？没有数学依据。把保底额先拆出去，剩下的部分再按比例分，每一步都有明确的规则，不会出现这种“凭感觉扣钱”的操作。

1.3 朴素四舍五入为什么不可行

另一个看起来可行、实测必挂的方案是四舍五入：先算出每个人的理想金额，四舍五入得到 b[i]，最后再检查总和。

问题在于，四舍五入根本不能保证总和守恒。三个人应得金额分别是 1.6、1.6、1.8，四舍五入后都变成 2，三者相加是 6，但 M 只有 5，凭空多出 1 元。反过来，如果四个人应得金额是 2.4、2.4、2.4、2.4，四舍五入后全部变成 2，总和 8，M 是 10，又少了 2 元。

有人会说，那我把多的减掉、少的补上不就行了？可以，但你按什么规则减？按什么规则补？这又回到了公平定义的问题。四舍五入只是在每个个体身上做独立近似，根本没有考虑总量守恒，它天然不是一个分配问题的解法。

所以，正确的算法必须先服务“总和精确等于 M”这个硬约束，再在满足约束的所有整数分配里寻找“公平”的那一个。最大余数法就是在这种思路下诞生的。

2. 最大余数法：一张表看懂分配逻辑

2.1 先向下取整，再按小数部分补足

最大余数法的流程看起来简单，但每一步背后都有原因。

设有 n 个人，每个人按比例应得的额外金额是 e[i] = C * p[i] / T。第一步，先给每个人 floor(e[i])，也就是直接抹掉小数部分。第二步，算出剩余未分配的金额 R = C - sum(floor(e[i]))。第三步，把所有 e[i] 的小数部分 frac(i) 拿出来从大到小排序，排名前 R 的人，每人再多拿 1 元。

为什么最后补的是 1 元而不是别的数？因为每个人被 floor 掉的零头都小于 1，而所有小数部分加在一起必然是一个 0 到 n-1 之间的整数，这个整数就是 R。所以补 1 元是最小可行单位，刚好把所有人的金额顶到 ceil(e[i])，不多不少。

这里有一个关键等式：sum(frac(i)) = R。这非常重要，它保证了前 R 个人的补足操作正好用完所有剩余金额，不会有盈余或者缺口。这个等式成立是因为 sum(e[i]) = C，而 sum(e[i]) = sum(floor(e[i])) + sum(frac(i))，C 是整数，sum(floor(e[i])) 是整数，所以 sum(frac(i)) 也必须是整数。既然每个人余数小于 1，那这个整数只可能在 0 到 n-1 之间。

我拿一组具体数据演算一遍。n = 4，p = [3, 1, 3, 1]，T = 8，M = 10。先保证每人 1 元，剩下 C = 6 用来按比例分配。

sum(floor) = 2 + 0 + 2 + 0 = 4，R = 6 - 4 = 2。小数部分最大的是第 1 个和第 3 个（0.75），所以这 2 元分别补给他们。最终额外金额：[2, 1, 2, 1]，加上保底 1 元，每个人最终拿到 [3, 2, 3, 2]，总和正好 10。

2.2 整数运算比浮点数可靠得多

上面表格里的 e[i] 我用小数写，是为了方便人看。实际写代码时，我坚决不用 double 去算这些小数，因为这里埋着一个很深的精度坑。

e[i] = C * p[i] / T 是一个分数。比较两个 e[i] 的小数部分谁更大，本质是比较 floor(e[i]) 之后的余数谁更大。余数定义为：

modVal[i] = (C * p[i]) % T

两个人余数的大小，直接对应小数部分 frac(i) 的大小，因为分母都是同一个 T。这样，最大余数法里的“按小数部分排序”就变成了“按 modVal[i] 降序排序”，全程没有任何浮点数参与。

为什么非要这样？假设 C 和 p[i] 都是 10^9 量级，乘积是 10^18，已经超过 double 能够精确表示的整数范围。double 在 10^18 这个量级上会有 6% 左右的浮点误差，导致排序结果出错。我再举个真实场景：两个人余数看起来一个是 0.5000000000001，另一个是 0.4999999999999，浮点数排序可能把它们排反，而整数取模完全不会犯这种错。

所以这题的隐藏考察点之一，就是你能不能意识到浮点数在“精确取整分配”场景下的局限性。用 long long 存乘积，用 % 取余数，用整型比较排序，所有问题迎刃而解。

2.3 最大余数法的局限性也要知道

既然谈到了分配方法，顺便说一句题外话。最大余数法在配额分配理论里是一种经典做法，但它并不完美，现实中会在某些特殊场景下出现反直觉的结果。不过 UVa 12259 这题考的是“在一个给定规则下求分配方案”，而不是“设计一种绝对完美的公平体系”，所以最大余数法就是这道题的标准答案之一。做题时你只需要保证自己输出的方案和题目定义的公平一致，不需要去解决完备性悖论。

这一点我觉得值得强调：竞赛题里的“公平”一定是题面里定义清楚的公平，不要自己脑补更高深的哲学意义，否则容易钻进牛角尖。

3. C++ 实现：整套代码与手算验证

3.1 结构体的设计

我定义一个人为一个结构体，原因是最大余数法的排序过程中，每个人需要携带的信息比较多：出资额、计算出的余数、输入顺序、最终分配金额。用一个 Node 结构体打包，后面排序和回填 ans 数组的时候非常方便。

struct Node { long long p; // 投入金额 long long get; // 按比例分到的额外部分（不含保底） long long mod; // (C * p[i]) % T，用于比较小数部分 int id; // 输入序号，用于稳定排序 };

这里 id 很关键。如果两个人余数完全相同，而待补金额只剩 1 元，排序结果将决定谁拿那 1 元。std::sort 不是稳定排序，如果只按 mod 比较，两个 mod 相等的人顺序可能不稳定，导致每次输出不同。加一个 id 作次级关键字，能保证输出可复现。

3.2 核心解题代码

下面给出完整代码。注释我写得比较多，方便直接照着理解。

#include <bits/stdc++.h> using namespace std; struct Node { long long p; long long get; long long mod; int id; }; bool fairDivision(int n, long long M, vector<long long>& p, vector<long long>& ans) { long long T = 0; for (long long x : p) T += x; // 每个人至少拿 1，所以奖金人数 if (M < n) return false; // 先扣除保底，剩下 C 参与按比例分配 long long C = M - n; vector<Node> a(n); if (T == 0) { // 总投入为 0，无法按比例分配，只能尽量平均。 long long base = C / n; long long rem = C % n; for (int i = 0; i < n; i++) { ans[i] = 1 + base + (i < rem ? 1 : 0); } return true; } long long allocated = 0; for (int i = 0; i < n; i++) { a[i].p = p[i]; a[i].id = i; a[i].get = (C * p[i]) / T; a[i].mod = (C * p[i]) % T; allocated += a[i].get; } long long remain = C - allocated; // 按余数（小数部分）从大到小排序，相同余数按下标排 sort(a.begin(), a.end(), [](const Node& u, const Node& v) { if (u.mod != v.mod) return u.mod > v.mod; return u.id < v.id; }); // 前 remain 个人各补 1 元 for (int i = 0; i < remain; i++) { a[i].get++; } // 写回答案，记得加上保底 1 元 for (int i = 0; i < n; i++) { ans[a[i].id] = a[i].get + 1; } return true; } int main() { // 每组数据调用 fairDivision，并输出 ans return 0; }

注意函数开头对 T == 0 的处理。这是防御性写法，出题数据未必有这种极端情况，但加上之后，你的代码面对非标准输入也不会崩溃。

还有一个细节：我计算 (C * p[i]) 时用的是 long long。如果 C 和 p[i] 的乘积可能超过 9e18，那 long long 也会溢出。好在 UVa 这类题的常规数据范围很少到这种量级，但不代表不需要知道。如果确实遇到，可以把中间计算换成 __int128，这个后面我会讲到。

3.3 手算验证一个更复杂的例子

我再用一组数据完整走一遍代码逻辑。设 n = 3，p = [2, 3, 5]，M = 17。

T = 10，M >= 3，所以 C = 17 - 3 = 14。

计算各自份额：

• 第 0 人：C * p / T = 14 * 2 / 10 = 2，余数 14 * 2 % 10 = 8；
• 第 1 人：14 * 3 / 10 = 4，余数 14 * 3 % 10 = 2；
• 第 2 人：14 * 5 / 10 = 7，余数 14 * 5 % 10 = 0。

allocated = 2 + 4 + 7 = 13，remain = 14 - 13 = 1。

按余数排序：第 0 人余数 8 最大，所以他获得补足的 1 元。最终额外分配为：

• 第 0 人：2 + 1 = 3；
• 第 1 人：4；
• 第 2 人：7。

加上保底 1 元，最终分得 [4, 5, 8]，总和 17。

再对比理想金额：17 * 0.2 = 3.4，17 * 0.3 = 5.1，17 * 0.5 = 8.5。最终结果 [4, 5, 8] 中，第 0 人向上取整，第 1 人向下取整，第 2 人向下取整。你会发现每个人拿到的值都没有跳出 floor(e[i]) 和 ceil(e[i]) 的范围，符合前面说的公平验收标准。

3.4 输出格式与本地校验

做题提交时，输出格式往往是第三个大坑。这道题每组数据输出一行，多个空格或末尾少换行都可能导致 Presentation Error 甚至 WA。

我在本地调试时，会在 fairDivision 函数结束后手动加一段校验逻辑：

long long sum = 0; for (long long v : ans) sum += v; if (sum != M) { cout << "allocation error" << endl; }

这段校验代码虽然不参与提交，但能帮你第一时间发现算法实现里的总和不守恒问题。只要你分发的逻辑有 bug，比如 remain 算错、补 1 补多了，这个 sum 一定对不上，比肉眼盯数字高效得多。

4. 实战中的三个坑：从 WA 到 AC 的排查过程

4.1 坑一：保底放错了位置，样例过但 WA

这是我在这道题上交出的第一版错误代码，值得拿出来复盘。

当时的逻辑是：直接把 M 按比例做最大余数法，分完如果发现有人分到 0，就把这个人改成 1，然后从当前分得最多的人身上减去同等金额，保证总和还是 M。样例数据恰好能过，因为样例里所有人的出资比例相对均衡，分到 0 的情况很少。

等到自测数据里出现一个出资极少的人，就暴露问题了。假设某人出资 1，总投入 100，奖金 100，n = 10。按比例分配时，出资 1 的人应得 1 元，floor 之后极可能是 0，然后我给他补成 1，再从某个大户身上扣 1。最终结果是出资 1 的人拿到 1，出资 50 的人反而少拿了 1。看起来还算合理，但题目规则是每个人都先保底 1，剩下 90 元按比例分配，出资 1 的人在剩余 90 元里应得的比例依然很小，他本来就不该再额外拿钱。

正确的保底顺序应该是“先保底、再分配”。把 M 拆成 n 元保底加 C 元比例分配之后，所有人的分配额都是“1 + 额外分配”，不会再出现补丁逻辑。这也是最大余数法版本能在数学上自洽的原因。

如果你也写了先分配后补保底的代码，建议直接删掉重写，不要想着在上面打补丁。后补逻辑会让代码充满特判，且每个特判都缺少理论依据。

4.2 坑二：int 溢出导致余数变成负数

第二个坑是我在本地构造大数数据时发现的。起初我图省事，所有金额变量用的都是 int，因为样例里数字很小，完全没意识到要开 long long。

当 C = 10^9，p[i] = 10^9 时，C * p[i] 等于 10^18，int 直接溢出成负数。负数的 % 操作在 C++ 里结果也是负数，排序时负数排在前面，分配结果完全乱掉。更阴险的是，这类错误在数据规模小的时候不会出现，一旦到了极限数据，程序会以非常“稳定”的方式给出完全错误但也完全符合格式的输出，让人排查很久。

我的做法是，凡是涉及金额乘法的地方，一律用 long long。如果题目没有明确说数据范围，我甚至会在本地跑一个把 p[i] 开到 10^12 的压力测试，确认乘积没有超过 long long。真到了需要超额范围的场景，可以把乘法临时转成 __int128：

__int128 prod = (__int128)C * p[i]; a[i].get = (long long)(prod / T); a[i].mod = (long long)(prod % T);

虽然大部分 OJ 不需要这样，但这个习惯能避免很多浪费时间的调试。

4.3 坑三：相同余数排序不稳定导致多提交几轮

第三个坑比较隐蔽。两个人余数相同，而 remain 恰好为 1，那么谁拿这 1 元就取决于排序顺序。我最早用 sort 只按 mod 降序排，没加 id 作次级关键字，本地跑了十次，有几次输出不同，有时候第一个人多拿 1 块，有时候第二个人多拿 1 块。本地手工检查时看着都符合规则，但交上去如果评测数据里存在这种并列，就会出现不可复现的问题。

最终处理方式就是代码里那样：排序比较函数里增加一个 id 作为次级关键字。这不仅是为了让输出稳定，更是一个好习惯——任何依赖排序顺序的贪心算法，都应该让排序规则是完备的，否则同样输入可能得到不同输出，这本身就是 bug 的信号。

4.4 从这道题抽象出通用模板

做完这道题之后，我把分配函数从主逻辑里抽离出来，整理成了一个通用的整数配额分配模板：输入 n 个权重和总配额 M，先处理保底额度，再按权重比例算整数份额，最后用最大余数法补齐总额。以后遇到类似的资源分配题，直接改数据类型就能用。

有一类题的变体是不要求每人保底 1 元，只要求每个人拿到的数额都为非负整数。处理起来更简单，只要把代码里的 M - n 换成 M，最后加 1 的部分去掉即可。另一类变体是权重可能为 0，这时需要保证分母 T > 0，并在总投入为 0 时走平均分配分支。

模板的价值在于，它可以让你省略大量重复推导。比如在做其他题目时，我把这个模板迁移到“按投票权重分配席位”的模拟题里，只改了几行输入输出就 AC 了。制作这种跨题复用的模板，也是刷题效率提升的一个关键点。

话说回来，UVa 12259 Fair Division 这道题难度本身不算高，真正的难点全藏在“整数”和“保底”这两个细节里。只要把保底顺序理清、整型运算用对、排序规则写全，代码量其实很少。我在实际调试中还有一个本地小技巧：每跑一组数据，都把 midstate 的 allocated、remain、最终 ans 打出来，和手算表格逐项对照，哪里不对一眼就能看出来。这一步帮我省下了大量反复提交的时间，也让我对最大余数法的直觉越来越清晰。