[学生代码修改] P14361社团招新

一、这道题真正的贪心思路假设有 4 个人每个人先选择自己满意度最高的部门。假如最终三个部门人数部门13人 部门21人 部门30人因为n4n 4n4每个部门最多222人。所以部门 1 多了111个人。我们必须把部门 1 的某个人调到其他部门。这时候应该找从最大满意度换成第二大满意度时损失最小的人。例如某A对3个部门的满意度如下部门1100 部门299 部门320那么从部门1调到部门2损失100−991损失 100 - 99 1损失100−991B对3个部门的满意度如下部门1100 部门250 部门330调走损失100−5050100 - 50 50100−5050显然应该优先调A。所以损失最大值−次大值损失 最大值 - 次大值损失最大值−次大值把超员部门所有人的损失从小到大排序然后取需要调走的那些人即可。二、原代码逐个错误分析你的结构体struct R{ int a,b,c; int mx,mi,mxi; int zxh,hxh,bxh;变量大概想表达变量含义a,b,c三个部门的满意度mx最大满意度mi最小满意度mxi中间的满意度也就是次大值zxh最大值所在部门hxh中间值所在部门bxh最小值所在部门错误 1最大值相同时zxh会被覆盖源代码if(mxa) zxh1; if(mxb) zxh2; if(mxc) zxh3;比如a10 b10 c5执行if(mxa) zxh1;此时zxh1但是继续if(mxb) zxh2;最后变成zxh2虽然这种情况下选部门 1 或部门 2 都可以但写法会产生覆盖。更严重的是a10 b10 c10最后zxh3这虽然还能勉强表示一个选择但你后面的hxh、bxh就彻底乱了。三、错误 2最小值同样会被覆盖你写if(mia) bxh1; if(mib) bxh2; if(mic) bxh3;例如10 5 5最后bxh3而不是唯一的部门。源代码hxh6-bxh-zxh;就不一定正确。四、错误 3hxh6-bxh-zxh依赖三个值必须不同例如a10 b10 c10可能得到zxh3 bxh3于是hxh6-3-3;得到hxh0;部门根本不存在。所以这段hxh6-bxh-zxh;不能这样写。五、错误 4不应该按照最大、第二大、最小依次给人分配原代码最核心的问题。if(r[j].zxh1an/2) { sumr[j].mx; a; }然后if(r[j].hxh1an/2) { sumr[j].mxi; a; }再if(r[j].bxh1an/2) { sumr[j].mi; a; }源代码的意思实际上是这个人如果第一志愿部门满了就尝试第二志愿再不行尝试第三志愿。但题目不是要求按输入顺序在线决定。真正应该第一步所有人先选择最大值。第二步统计三个部门人数。第三步如果某个部门超过n/2n/2n/2只从这个部门的人里面挑人调走而且挑最大值−次大值最大值 - 次大值最大值−次大值最小的人。六、错误 5 n/2写错了你写if(r[j].zxh1an/2)假设n4 n/22当a2你的条件a2仍然成立。然后a;结果a3部门 1 就有 3 个人了。题目要求的是人数≤n/2人数 \leq n/2人数≤n/2如果准备继续加入一个人那么应该判断an/2a n/2an/2而不是a≤n/2a \leq n/2a≤n/2七、错误 6写错变量了源代码if(r[j].bxh3cn/2) { sumr[j].mi; a; }这里判断的是c说明想给第 3 部门加人。但是最后写成了a;应该是c;八、错误 7没有处理超员以后重新调整比如n4如果最优选择以后部门13 部门21 部门30那么部门1必须调走1个人。原代码是在读取每个人的时候就决定if(...)但是你不知道后面的人会不会导致某个部门超员。所以应该先全部选最大值 ↓ 统计人数 ↓ 发现部门1超员 ↓ 重新从部门1里面挑人这就是所谓的先贪心再调整。九、错误 8mxi的意义其实是次大值你写mxiabc-mx-mi;数学上确实可以得到中间值。例如4 2 1那么421−4−12421-4-12421−4−12得到mxi2这个计算本身没有问题。但是由于前面的zxh bxh hxh在出现相等值的时候可能错误所以后面不能可靠地知道mxi究竟属于哪个部门不过其实这题根本不需要知道次大值属于哪个部门。因为调走以后直接去次大满意度对应的部门即可。而且那个部门一定不会超过n/2n/2n/2。十、为什么调到次大部门一定安全这是这道题最重要的一个结论。假设部门 1 超过n/2n/2n/2比如n10 部门16 部门23 部门31我们从部门1调人。部门2和部门3原本加起来314314314而454 545所以即使我们把人调到部门2部门2最多变成5部门2最多变成5部门2最多变成5也不会超过n/2n/2n/2。因此只要某个部门超过n/2n/2n/2那么其他两个部门都不可能超过n/2n/2n/2。这也是为什么我们只需要把超员部门的人调到他的次大满意度部门即可。十一、修改后的代码按照原代码的格式继续使用结构体继续使用数组变量尽量保留源代码的风格#includebits/stdc.husingnamespacestd;constintI1e55;//测试数据组数intt;//学生人数intn;//最终答案longlongsum;//每个学生的信息structR{inta,b,c;//三个部门的满意度intmx;//最大满意度intmi;//最小满意度intmxi;//次大满意度intzxh;//最大值所在的部门};//保存每个人的信息R r[I];/* 按照最大值-次大值从小到大排序 这个值代表 如果这个人原本选择满意度最高的部门 现在把他调到第二满意的部门 总满意度会损失多少。 损失越小越应该优先调走。 */boolcmp(R x,R y){returnx.mx-x.mxiy.mx-y.mxi;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cint;while(t--){//初始化sum0;//三个部门当前人数inta0;intb0;intc0;cinn;/* 第一步 暂时不考虑部门人数限制。 每个人直接选择自己满意度最高的部门。 */for(intj1;jn;j){cinr[j].ar[j].br[j].c;//求最大值r[j].mxmax(r[j].a,max(r[j].b,r[j].c));//求最小值r[j].mimin(r[j].a,min(r[j].b,r[j].c));/* 三个数的和 -最大值 -最小值 就等于中间的那个数也就是次大值。 */r[j].mxir[j].ar[j].br[j].c-r[j].mx-r[j].mi;/* 确定这个人原本选择哪个部门。 如果出现相同最大值 选择其中任意一个都可以。 使用/else if 保证只选择一个部门。 */if(r[j].ar[j].br[j].ar[j].c){r[j].zxh1;a;}elseif(r[j].br[j].ar[j].br[j].c){r[j].zxh2;b;}else{r[j].zxh3;c;}//先把每个人的最大满意度加入答案sumr[j].mx;}/* 第二步 判断三个部门有没有超过n/2。 因为三个部门总人数只有n 所以不可能有两个部门同时超过n/2。 因此最多只有一个部门超员。 */intbad0;if(an/2)bad1;elseif(bn/2)bad2;elseif(cn/2)bad3;/* 如果bad0 说明三个部门人数都没有超过n/2 当前所有人选择最大值的方案 本身就是最优答案。 不需要进行任何调整。 */if(bad0){coutsumendl;continue;}/* 第三步 找到了超员部门。 例如 n10 部门17 部门22 部门31 那么部门1必须调走 7-52 个人。 我们只需要从原本选择部门1的人里面 找最大值-次大值最小的人。 因为 最大值-次大值 损失越小越好。 *///对所有人按照最大值-次大值排序sort(r1,rn1,cmp);//需要从超员部门调走多少人intneed;if(bad1)needa-n/2;elseif(bad2)needb-n/2;elseneedc-n/2;/* 第四步 按照损失从小到大 从超员部门中选择need个人调走。 */for(intj1;jnneed0;j){//只处理原本属于超员部门的人if(r[j].zxhbad){/* 这个人从最大满意度 换成次大满意度 所以答案减少 mx-mxi */sum-r[j].mx-r[j].mxi;need--;}}//输出最终答案coutsumendl;}}十二、代码核心其实只有这几步① 每个人先选最大值 ↓ ② 统计三个部门人数 ↓ ③ 找有没有部门 n/2 ↓ ④ 如果没有直接输出 ↓ ⑤ 如果有 找这个部门多出来多少人 ↓ ⑥ 计算每个人 最大值 - 次大值 ↓ ⑦ 从小到大排序 ↓ ⑧ 取最小的几个 ↓ ⑨ 从答案中减掉这些损失也就是先让所有人选第一志愿如果第一志愿的人太多就把改去第二志愿损失最小的人调走。这就是这题的核心。十三、原代码和 AC 代码最大的区别原来的思路是第1个人来了 ↓ 能去最大就去最大 ↓ 不行就去第二大 ↓ 再不行去最小 第2个人来了 ↓ 继续这样判断这是边读边分配。而正确思路是所有人先选最大 ↓ 统计结果 ↓ 发现部门1超员 ↓ 回头看部门1的所有人 ↓ 找最大-次大最小的人 ↓ 把这些人调走也就是原来的代码是边走边决定正确代码是先做最优初始方案再进行全局调整。十四、再特别提醒一个容易误解的地方原来专门记录zxh hxh bxh其实这题不需要记录次大值所在的部门。我们只需要知道mx // 最大值 mxi // 次大值 zxh // 最大值属于哪个部门就够了。因为当某部门超员以后这个人从最大值部门调走 ↓ 直接去次大值对应的部门不需要知道它具体是部门 1、2 还是 3。所以我把你的hxh bxh删掉了代码反而更简单也避免了最大值/最小值相等时部门编号混乱的问题。这题的时间复杂度是O(nlog⁡n)O(n \log n)O(nlogn)主要来自排序n≤105n \leq 10^5n≤105可以轻松通过。