: 学习小组)
2025年12月GESP真题及题解(C++七级): 学习小组
题目描述
班主任计划将班级里的n nn名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号，第i ii名同学有其发言积极度c i c_ici。
观察发现，如果一个学习小组中恰好包含编号为p 1 , p 2 , … , p k p_1,p_2,\ldots,p_kp1,p2,…,pk的k kk名同学，则该学习小组的基础讨论积极度为a k a_kak，综合讨论积极度为a k + max { c p 1 , c p 2 , … , c p k } − min { c p 1 , c p 2 , … , c p k } a_k+\max\{c_{p_1},c_{p_2},\ldots,c_{p_k}\}−\min\{c_{p_1},c_{p_2},\ldots,c_{p_k}\}ak+max{cp1,cp2,…,cpk}−min{cp1,cp2,…,cpk}，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。
给定基础讨论积极度a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an，请你计算将这n nn名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。
输入格式
第一行，一个正整数n nn，表示班级人数。
第二行，n nn个非负整数c 1 , c 2 , … , c n c_1,c_2,\ldots,c_nc1,c2,…,cn，表示每位同学的发言积极度。
第三行，n nn个非负整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an，表示不同人数学习小组的基础讨论积极度。
输出格式
输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。
输入输出样例 #1
输入 #1
4 2 1 3 2 1 5 6 3输出 #1
12输入输出样例 #2
输入 #2
8 1 3 2 4 3 5 4 6 0 2 5 6 4 3 3 4输出 #2
21说明/提示
对于40 % 40\%40%的测试点，保证c i = 0 c_i=0ci=0。
对于所有测试点，保证1 ≤ n ≤ 300 1\le n\le 3001≤n≤300，0 ≤ c i ≤ 10 4 0\le c_i\le 10^40≤ci≤104，0 ≤ a i ≤ 10 4 0\le a_i\le 10^40≤ai≤104。
思路分析
题目要求将n nn个同学划分成若干个学习小组，使得所有小组的综合讨论积极度之和最大。每个小组的得分由基础积极度a k a_kak和组内最大最小发言积极度之差组成。
通过分析，我们可以将问题转化为：将同学按发言积极度c i c_ici排序后，选择m mm个小组（每组至少两人），这些小组的最小值取排序后最小的m mm个值，最大值取排序后最大的m mm个值，并且一一配对。剩下的同学作为中间同学分配到这些小组中，或者作为单独小组（每组一人）。通过动态规划计算最优分配，从而得到最大总得分。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=305;intc[N],a[N];intf[N][N];// f[m][s] 表示 m 个小组分配 s 个中间同学的最大 sum(a_{2+t_i})intmain(){intn;cin>>n;for(inti=0;i<n;i++)cin>>c[i];for(inti=0;i<n;i++)cin>>a[i];sort(c,c+n);// 按发言积极度排序// 初始化 f 为负无穷，f[0][0] = 0for(inti=0;i<=n/2;i++){for(intj=0;j<=n;j++){f[i][j]=-1e9;}}f[0][0]=0;// 预处理 f[m][s]for(intm=1;m<=n/2;m++){intmax_s=n-2*m;// 中间同学最多有 n-2m 个for(ints=0;s<=max_s;s++){for(intt=0;t<=s;t++){// 当前小组分配 t 个中间同学if(1+t<n){// a[1+t] 对应 a_{2+t}f[m][s]=max(f[m][s],f[m-1][s-t]+a[1+t]);}}}}intans=0;// 枚举小组数量 mfor(intm=0;m<=n/2;m++){intr=n-2*m;// 剩余同学数量（可能作为中间同学或单独小组）// 计算极差贡献：最小的 m 个和最大的 m 个配对intdiff_sum=0;for(inti=0;i<m;i++){diff_sum+=c[n-1-i]-c[i];}// 枚举中间同学数量 sfor(ints=0;s<=r;s++){intscore=diff_sum+f[m][s]+(r-s)*a[0];// a[0] 对应 a_1ans=max(ans,score);}}cout<<ans<<endl;return0;}算法分析
- 排序：首先将同学按发言积极度c i c_ici从小到大排序。
- 动态规划预处理：
- 定义
f[m][s]表示有m mm个小组（每组至少两人），分配s ss个中间同学时，这些小组的基础积极度之和的最大值。 - 转移方程：
f[m][s] = max_{t=0..s} f[m-1][s-t] + a[2+t]，其中t tt是当前小组分配的中间同学数。
- 定义
- 枚举与计算：
- 枚举小组数m mm（0 ≤ m ≤ n / 2 0 \le m \le n/20≤m≤n/2），计算剩余同学数r = n − 2 m r = n - 2mr=n−2m。
- 计算极差贡献：最小的m mm个c i c_ici与最大的m mm个c i c_ici一一配对，求和c max − c min c_{\text{max}} - c_{\text{min}}cmax−cmin。
- 枚举中间同学数s ss（0 ≤ s ≤ r 0 \le s \le r0≤s≤r），计算总得分：极差贡献 +
f[m][s]+ 单独小组贡献( r − s ) × a 1 (r-s) \times a_1(r−s)×a1。
- 输出最大值。
复杂度分析
- 时间复杂度：O ( n 3 ) O(n^3)O(n3)，其中n ≤ 300 n \le 300n≤300，三重循环（枚举m mm、s ss和t tt）可接受。
- 空间复杂度：O ( n 2 ) O(n^2)O(n2)，用于存储
f数组。
各种学习资料，助力大家一站式学习和提升！！！
#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;}
