2025信奥赛C++提高组csp-s复赛真题及题解：社团招新
2025信奥赛C++提高组csp-s复赛真题及题解：社团招新
题目描述
小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了n nn个新成员，其中n nn为偶数。现在小 L 希望将他们分到协会不同的部门。
算法协会共设有三个部门，其中第i ii(1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n) 个新成员对第j jj(1 ≤ j ≤ 3 1 \leq j \leq 31≤j≤3) 个部门的满意度为a i , j a_{i,j}ai,j。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第i ii(1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n) 个新成员分配到了第d i ∈ { 1 , 2 , 3 } d_i \in \{1,2,3\}di∈{1,2,3}个部门，则该分配方案的满意度为∑ i = 1 n a i , d i \sum_{i=1}^{n} a_{i,d_i}∑i=1nai,di。
小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于n 2 \frac{n}{2}2n个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。
输入格式
本题包含多组测试数据。
输入的第一行包含一个正整数t tt，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
- 第一行包含一个正整数n nn，表示新成员的数量。
- 第i + 1 i+1i+1(1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n) 行包含三个非负整数a i , 1 , a i , 2 , a i , 3 a_{i,1}, a_{i,2}, a_{i,3}ai,1,ai,2,ai,3，分别表示第i ii个新成员对第1 , 2 , 3 1,2,31,2,3个部门的满意度。
输出格式
对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。
输入输出样例 1
输入 1
3 4 4 2 1 3 2 4 5 3 4 3 5 1 4 0 1 0 0 1 0 0 2 0 0 2 0 2 10 9 8 4 0 0输出 1
18 4 13说明/提示
【样例 1 解释】
该样例共包含三组测试数据。
对于第一组测试数据，可以将四个新成员分别分配到第1 , 3 , 1 , 2 1,3,1,21,3,1,2个部门，则三个部门的新成员数量分别为2 , 1 , 1 2,1,12,1,1，均不超过4 2 = 2 \frac{4}{2} = 224=2，满意度为4 + 4 + 5 + 5 = 18 4 + 4 + 5 + 5 = 184+4+5+5=18。
对于第二组测试数据，可以将四个新成员分别分配到第1 , 1 , 2 , 2 1,1,2,21,1,2,2个部门，则三个部门的新成员数量分别为2 , 2 , 0 2,2,02,2,0，均不超过4 2 = 2 \frac{4}{2} = 224=2，满意度为0 + 0 + 2 + 2 = 4 0 + 0 + 2 + 2 = 40+0+2+2=4。
对于第三组测试数据，可以将两个新成员分别分配到第2 , 1 2,12,1个部门，则三个部门的新成员数量分别为1 , 1 , 0 1,1,01,1,0，均不超过2 2 = 1 \frac{2}{2} = 122=1，满意度为9 + 4 = 13 9 + 4 = 139+4=13。
【数据范围】
对于所有测试数据，保证：
- 1 ≤ t ≤ 5 1 \leq t \leq 51≤t≤5;
- 2 ≤ n ≤ 10 5 2 \leq n \leq 10^52≤n≤105，且n nn为偶数;
- 对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，1 ≤ j ≤ 3 1 \leq j \leq 31≤j≤3，均有0 ≤ a i , j ≤ 2 × 10 4 0 \leq a_{i,j} \leq 2 \times 10^40≤ai,j≤2×104。
| 测试点编号 | n = n=n= | 特殊性质 |
|---|---|---|
| 1 11 | 2 22 | 无 |
| 2 22 | 4 44 | ^ |
| 3 , 4 3, 43,4 | 10 1010 | ^ |
| 5 ∼ 8 5 \sim 85∼8 | 30 3030 | ^ |
| 9 99 | 200 200200 | B |
| 10 , 11 10, 1110,11 | ^ | 无 |
| 12 1212 | 10 5 10^5105 | A |
| 13 , 14 13, 1413,14 | ^ | B |
| 15 , 16 15, 1615,16 | ^ | C |
| 17 ∼ 20 17 \sim 2017∼20 | ^ | 无 |
特殊性质 A：对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，均有a i , 2 = a i , 3 = 0 a_{i,2} = a_{i,3} = 0ai,2=ai,3=0。
特殊性质 B：对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，均有a i , 3 = 0 a_{i,3} = 0ai,3=0。
特殊性质 C：对于所有1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n，1 ≤ j ≤ 3 1 \leq j \leq 31≤j≤3，a i , j a_{i,j}ai,j均在[ 0 , 2 × 10 4 ] [0, 2 \times 10^4][0,2×104]中独立均匀随机生成。
思路分析
这是一个关于社团招新分配的优化问题。需要将n个成员分配到3个部门，每个部门人数不超过n/2，目标是最大化总满意度。我们采用反悔贪心算法来解决这个问题。
算法核心思路
- 贪心初始化：首先让每个成员选择满意度最高的部门
- 处理超员：如果某个部门人数超过n/2，需要进行调整
- 最小化损失：优先调整那些调整代价（满意度损失）最小的成员
由于n为偶数且三个部门人数总和为n，数学上可以证明：最多只有一个部门会超过n/2。这是因为如果两个部门都超过n/2，总人数就会超过n。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intt,n;// 存储每个成员对三个部门的满意度structnode{intd1,d2,d3;// 分别表示对部门1、2、3的满意度}a[N];intb[N];// 记录每个成员初始选择的部门编号intmain(){cin>>t;// 读取测试数据组数while(t--){cin>>n;// 读取成员数量// 读取每个成员对三个部门的满意度for(inti=1;i<=n;i++){cin>>a[i].d1>>a[i].d2>>a[i].d3;}longlongans=0;// 总满意度，使用long long防止溢出intcnt1=0,cnt2=0,cnt3=0;// 记录三个部门当前的人数// 第一步：贪心初始化 - 每个成员选择满意度最高的部门for(inti=1;i<=n;i++){if(a[i].d1>=a[i].d2&&a[i].d1>=a[i].d3){// 部门1满意度最高或并列最高b[i]=1;// 记录选择部门1cnt1++;// 部门1人数增加ans+=a[i].d1;// 累加满意度}elseif(a[i].d2>=a[i].d1&&a[i].d2>=a[i].d3){// 部门2满意度最高或并列最高b[i]=2;cnt2++;ans+=a[i].d2;}else{// 部门3满意度最高或并列最高b[i]=3;cnt3++;ans+=a[i].d3;}}// 第二步：检查是否有部门超员，并计算调整代价vector<int>v;// 存储需要调整的成员的"损失值"for(inti=1;i<=n;i++){// 如果部门1超员且当前成员选择了部门1if(cnt1>n/2&&b[i]==1){// 计算从部门1调整到其他部门的最大损失// 损失 = 当前满意度 - 其他两个部门中较高的满意度v.push_back(a[i].d1-max(a[i].d2,a[i].d3));}// 如果部门2超员且当前成员选择了部门2elseif(cnt2>n/2&&b[i]==2){v.push_back(a[i].d2-max(a[i].d1,a[i].d3));}// 如果部门3超员且当前成员选择了部门3elseif(cnt3>n/2&&b[i]==3){v.push_back(a[i].d3-max(a[i].d1,a[i].d2));}}// 第三步：对损失值进行排序，优先调整损失最小的成员sort(v.begin(),v.end());// 第四步：执行调整，减少超员部门的人数inti=0;// 用于遍历已排序的损失值// 调整部门1的超员人员while(cnt1>n/2){ans-=v[i++];// 减去调整损失cnt1--;// 部门1人数减少}// 调整部门2的超员人员while(cnt2>n/2){ans-=v[i++];cnt2--;}// 调整部门3的超员人员while(cnt3>n/2){ans-=v[i++];cnt3--;}// 输出最终的最大满意度cout<<ans<<endl;}return0;}功能分析
1.贪心初始化阶段
- 每个成员独立选择满意度最高的部门
- 记录每个成员的选择和部门人数
- 计算初始总满意度
2.超员检测与调整准备
- 检查是否有部门人数超过n/2
- 对于超员部门的每个成员，计算如果调整到次优部门的满意度损失
- 将损失值收集到数组中
3.调整执行阶段
- 对损失值进行升序排序（最小损失优先）
- 依次调整损失最小的成员，直到部门人数不超过n/2
- 每次调整从总满意度中减去相应的损失值
4.数学正确性保证
- 由于n为偶数，最多只有一个部门会超过n/2
- 调整后，其他部门不会因为接收调整的成员而超员
- 每次调整都选择损失最小的成员，保证最终总满意度最大化
5. 时间复杂度分析
- 贪心初始化：O(n)
- 计算调整损失：O(n)
- 排序损失值：O(k log k)，其中k为需要调整的成员数量（最多n/2）
- 总时间复杂度：O(n log n)，满足题目数据范围要求（n ≤ 105 ^55）
6. 空间复杂度分析
- 存储成员满意度：O(n)
- 存储调整损失：O(k) ≤ O(n)
- 总空间复杂度：O(n)
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}