★ FEATURED ARTICLE 做 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总和 8M 是 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 4p [3, 1, 3, 1]T 8M 10。先保证每人 1 元剩下 C 6 用来按比例分配。序号p[i]e[i]floor(e[i])frac(i)032.2520.25110.7500.75232.2520.25310.7500.75sum(floor) 2 0 2 0 4R 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, vectorlong long p, vectorlong 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; vectorNode 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 3p [2, 3, 5]M 17。T 10M 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 13remain 14 - 13 1。按余数排序第 0 人余数 8 最大所以他获得补足的 1 元。最终额外分配为第 0 人2 1 3第 1 人4第 2 人7。加上保底 1 元最终分得 [4, 5, 8]总和 17。再对比理想金额17 * 0.2 3.417 * 0.3 5.117 * 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奖金 100n 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^9p[i] 10^9 时C * p[i] 等于 10^18int 直接溢出成负数。负数的 % 操作在 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 打出来和手算表格逐项对照哪里不对一眼就能看出来。这一步帮我省下了大量反复提交的时间也让我对最大余数法的直觉越来越清晰。
阅读完成 · 觉得有帮助？
区别)
