题目描述美国宪法规定众议员名额应按各州人口比例分配且每州至少一名。但由于人口并非除得尽实际分配必须给每个州一个正整数个席位。本题要求对给定的若干州的人口数和目标总席位数分别用四种经典分配方法Hamilton\texttt{Hamilton}Hamilton、Jefferson\texttt{Jefferson}Jefferson、Adams\texttt{Adams}Adams、Webster\texttt{Webster}Webster计算每个州的席位数并指出对于每个州哪种方法如果有给予该州的席位严格多于其他方法。具体地有nnn个州n≤50n \le 50n≤50每个州有唯一名称恰好555个字符和正整数人口。对于每个目标总席位数HHHH≥nH \ge nH≥n输出每个州的比较结果。输入格式输入包含多组数据。每组数据第一行为州数nnn。若n0n 0n0则输入结束。接下来nnn行每行一个州名恰好555个字符从第111列开始和一个正整数人口二者之间至少一个空格。之后是一行或多行整数每行一个目标席位数HHH。输入以单独的000表示该组数据的HHH列表结束。保证HHH不小于州数nnn。输出格式对于每组数据先输出Data set k:kkk从111开始。对于每个目标席位数HHH输出一行For H representatives:对每个州按输入顺序输出一行格式为若所有方法得到的席位数相同则输出州名 is favored by no method.否则输出州名 is favored by 方法1 and 方法2 ... .其中方法名按固定顺序Hamilton、Jefferson、Adams、Webster列出所有达到最大值的那些方法方法名之间用and连接末尾句点。每个HHH的输出后跟一个空行。样例输入5 Anxit 42 Bored 178 Confu 221 Dismy 117 Ecsta 72 30 5 0 0输出Data set 1: For 30 representatives: Anxit is favored by no method. Bored is favored by Jefferson. Confu is favored by Hamilton and Jefferson and Webster. Dismy is favored by Hamilton and Adams and Webster. Ecsta is favored by Adams. For 5 representatives: Anxit is favored by no method. Bored is favored by no method. Confu is favored by no method. Dismy is favored by no method. Ecsta is favored by no method.题目分析本题的核心是议席分配问题。给定总人口total\textit{total}total和目标席位数HHH一个“公平”的理想分配是每个州获得popi×H/total\textit{pop}_i \times H / \textit{total}popi×H/total个席位但该值通常非整数。四种方法以不同方式将小数部分“舍入”或“调整”使得总和恰好为HHH。各方法原理Hamilton\texttt{Hamilton}Hamilton最大余数法先取每个州配额的整数部分保证至少111席剩余席位按小数部分从大到小分配。这是一种直观且符合直觉的方法但可能产生“阿拉巴马悖论”增加总席位反致某些州席位减少但本题无需考虑。Jefferson\texttt{Jefferson}Jefferson向下取整除数法寻找一个除数ddd使得对每个州⌊popi/d⌋\lfloor \textit{pop}_i / d \rfloor⌊popi/d⌋的和等于HHH。等价于“最高均值法”中分母为(当前席位数1)(\text{当前席位数}1)(当前席位数1)的分配过程初始每州111席反复将下一个席位给popi/(当前席位数1)\textit{pop}_i / (\text{当前席位数}1)popi/(当前席位数1)最大的州。Adams\texttt{Adams}Adams向上取整除数法寻找除数ddd使得⌈popi/d⌉\lceil \textit{pop}_i / d \rceil⌈popi/d⌉的和等于HHH。等价于分母为当前席位数\text{当前席位数}当前席位数的最高均值法。Webster\texttt{Webster}Webster四舍五入除数法寻找除数ddd使得popi/d\textit{pop}_i / dpopi/d按四舍五入后求和等于HHH。等价于分母为(2×当前席位数1)(2 \times \text{当前席位数} 1)(2×当前席位数1)的最高均值法Sainte‑Laguë 方法。由于HHH可能远大于nnn直接枚举除数不可行。但最高均值法用优先队列模拟分配过程每次只增加一个席位复杂度O((H−n)logn)O((H-n) \log n)O((H−n)logn)在本题HHH大小未明确但显然可接受输入规模小。比较规则对于每个州需要比较四种方法返回的席位数。如果所有方法的数值相同则没有任何方法“给予更多”否则找出最大值列出所有达到该最大值的方法名。注意必须严格大于其他方法即如果最大值出现多次并列第一这些并列的方法都应列出因为它们都比未达到最大值的其他方法多。解题思路总体框架读入州数据。对于每个目标席位数HHH分别用四种方法计算各州席位。对每个州比较四个值按规则输出。各方法实现细节Hamilton\texttt{Hamilton}Hamilton方法计算总人口total使用long long。对每个州iii计算乘积prod pop[i] * H整数部分q prod / total余数rem prod % total。初始席位为max(1, q)并累加已分配数。将余数即小数部分按从大到小排序只考虑“真实配额 ≥ 1”的州即prod total依次给这些州加111席直到剩余席位分配完毕。注意当q 0时已保证至少111席但该州在余数分配时不参与因为配额小于111的州不应获得额外席位。Jefferson\texttt{Jefferson}Jefferson、Adams\texttt{Adams}Adams、Webster\texttt{Webster}Webster方法三者统一用优先队列最大堆模拟最高均值法初始每个州分配111席题目保证H≥nH \ge nH≥n。定义“价值”函数Jefferson\texttt{Jefferson}Jeffersonvaluepop/(当前席位1)\textit{value} \textit{pop} / (\text{当前席位} 1)valuepop/(当前席位1)Adams\texttt{Adams}Adamsvaluepop/当前席位\textit{value} \textit{pop} / \text{当前席位}valuepop/当前席位Webster\texttt{Webster}Webstervaluepop/(2×当前席位1)\textit{value} \textit{pop} / (2 \times \text{当前席位} 1)valuepop/(2×当前席位1)重复H−nH-nH−n次弹出当前价值最大的州为其增加111席重新计算该州新价值并压入堆。由于每次弹出后该州的价值会变化优先队列中可能残留旧值。在弹出时检查该值是否仍等于该州当前的实际价值用极小误差比较若不是则丢弃并继续弹出。比较与输出对每个州获得四个整数数组h[i]、j[i]、a[i]、w[i]。计算最大值mx和最小值mn。若mx mn说明全部相等输出no method否则按顺序检查四个值若等于mx则记录方法名。输出时用and连接。复杂度分析每次Hamilton\texttt{Hamilton}Hamilton计算O(nlogn)O(n \log n)O(nlogn)排序余数。每次最高均值法模拟O((H−n)logn)O((H-n) \log n)O((H−n)logn)但HHH在输入中未给出上界但n≤50n \le 50n≤50且席位数显然不会过大样例中HHH为303030和555实际数据应保证算法可行。总时间复杂度对每组数据每个HHHO((H−n)lognnlogn)O((H-n) \log n n \log n)O((H−n)lognnlogn)在合理范围内。空间复杂度O(n)O(n)O(n)。代码实现// Constitutional Computing// UVa ID: 364// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structState{string name;longlongpop;};// Hamilton 方法最大余数法vectorinthamilton(constvectorStatestates,intH){intn(int)states.size();longlongtotal0;for(autos:states)totals.pop;vectorintreps(n);intsum0;vectorlonglongrem(n);for(inti0;in;i){longlongprodstates[i].pop*H;longlongqprod/total;// 整数部分rem[i]prod%total;// 余数小数部分的分母固定为 totalreps[i](int)q;if(reps[i]1)reps[i]1;sumreps[i];}intleftH-sum;vectorintidx;for(inti0;in;i)if(states[i].pop*Htotal)idx.push_back(i);// 真实配额 1sort(idx.begin(),idx.end(),[](inta,intb){if(rem[a]!rem[b])returnrem[a]rem[b];returnab;});for(inti0;ilefti(int)idx.size();i)reps[idx[i]];returnreps;}// 通用除数法优先队列模拟vectorintdivisorMethod(constvectorStatestates,intH,functionlonglong(int)denom){intn(int)states.size();vectorintreps(n,1);if(Hn)returnreps;priority_queuepairlongdouble,intpq;for(inti0;in;i){longdoubleval(longdouble)states[i].pop/denom(reps[i]);pq.push({val,i});}intremainH-n;while(remain0){while(true){autocurpq.top();pq.pop();inticur.second;longdoublecurVal(longdouble)states[i].pop/denom(reps[i]);if(fabsl(cur.first-curVal)1e-12L){// 有效元素reps[i];longdoublenewVal(longdouble)states[i].pop/denom(reps[i]);pq.push({newVal,i});remain--;break;}// 否则丢弃过时的旧值}}returnreps;}// Jefferson分母 rep 1vectorintjefferson(constvectorStatestates,intH){returndivisorMethod(states,H,[](intrep){returnrep1;});}// Adams分母 repvectorintadams(constvectorStatestates,intH){returndivisorMethod(states,H,[](intrep){returnrep;});}// Webster分母 2 * rep 1vectorintwebster(constvectorStatestates,intH){returndivisorMethod(states,H,[](intrep){return2LL*rep1;});}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intdataset1;intn;while(cinnn!0){vectorStatestates(n);for(inti0;in;i)cinstates[i].namestates[i].pop;coutData set dataset:\n;intH;while(cinHH!0){vectorinthhamilton(states,H);vectorintjjefferson(states,H);vectorintaadams(states,H);vectorintwwebster(states,H);coutFor H representatives:\n;for(inti0;in;i){intvals[4]{h[i],j[i],a[i],w[i]};intmxvals[0],mnvals[0];for(intk1;k4;k){if(vals[k]mx)mxvals[k];if(vals[k]mn)mnvals[k];}vectorstringmethods;if(mx!mn){// 存在某个方法严格大于其他方法if(vals[0]mx)methods.push_back(Hamilton);if(vals[1]mx)methods.push_back(Jefferson);if(vals[2]mx)methods.push_back(Adams);if(vals[3]mx)methods.push_back(Webster);}coutstates[i].name is favored by ;if(methods.empty()){coutno method.\n;}else{for(size_t k0;kmethods.size();k){if(k0)cout and ;coutmethods[k];}cout.\n;}}cout\n;// 每个代表数后空一行}dataset;}return0;}总结本题虽然背景复杂但核心算法并不难关键在于理解四种分配方法的等价最高均值实现以及正确比较各方法结果。主要收获最高均值法的通用模拟用优先队列按不同分母动态分配席位避免了除法收敛问题。浮点数比较用fabsl和极小的容忍误差处理long double值的相等性避免因精度问题导致死循环。并列第一的处理注意“更多”意味着严格大于因此必须检查最大值与最小值是否相等若相等则无任何方法占优。输入输出细节注意每组数据中HHH以000结束且每个HHH后要输出空行。这种题目的实现技巧优先队列 函数对象也适用于其他类似的分配或调度问题。
