GESP2025 年 12 月 C++ 七级真题解析：学习小组分组问题

一、原题描述

二、题目解析

1. 故事背景

班主任要把全班同学分成学习小组。

• 一共 n 个同学
• 每个同学都有一个发言积极度
• 每个学习小组要求：
  • 所有人必须被分进去
  • 不能重叠

2. 分数计算规则

每个学习小组的得分由两部分组成：

(1) 基础讨论积极度

只和小组人数有关。人数是 k，就加 a[k]。

(2) 额外热闹值

小组里最爱说话的同学（最大值）与最不爱说话的同学（最小值）之差。 公式：额外值 = 最大 - 最小

3. 目标

想办法分组，让所有小组的综合讨论积极度之和最大。

4. 示例分析

假设有 4 个同学，编号 1 到 4，积极度分别为 2, 1, 3, 2。 基础分数组 a 为：a[1]=1, a[2]=5, a[3]=6, a[4]=3。

• 方案一：每人一组

  • [2], [1], [3], [2]
  • 每组基础分 = a[1] = 1，额外值 = 0
  • 总分 = 4

• 方案二：全班一组

  • [2, 1, 3, 2]
  • 基础分 = a[4] = 3
  • 最大 = 3，最小 = 1，额外 = 2
  • 总分 = 5

• 方案三：分成两组

  • [2, 1], [3, 2]
  • 第一组：基础 = 5，差值 = 2 - 1 = 1
  • 第二组：基础 = 5，差值 = 3 - 2 = 1
  • 总分 = 12

5. 解题思路

暴力枚举所有分组方式会导致方案数爆炸，因此必须使用动态规划（DP）。

(1) 排序的重要性

在 DP 之前需要先对积极度进行排序：sort(c + 1, c + n + 1)。 排序后，最小值在前，最大值在后，方便计算 最大 - 最小。

核心结论：如果目标是最大化差值，一定要把最小的和最大的放在同一组。中间的人是谁，对差值没有影响。

(2) DP 状态定义

f[j][k] 表示用 k 个同学分成 j 个小组能得到的最大综合讨论积极度。

(3) 状态转移

假设最后一个小组有 i 个人，前面用了 k - i 个同学，前面有 j - 1 个小组。 转移公式：

f[j][k] = max(f[j-1][k-i] + a[i] + (当前组最大值 - 当前组最小值))

其中，当前组的极值可以通过排序后的数组下标直接获取。

6. 完整代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 305;
int n;
int c[N], a[N];
int f[N][N];
int ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    sort(c + 1, c + n + 1);
    
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= n; j++)
            for (int k = i; k <= n; k++) {
                int diff = 0;
                if (i > 1) diff = c[n - j + 1] - c[j];
                f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);
                if (k == n) ans = max(ans, f[j][k]);
            }
    
    printf("%d\n", ans);
    return 0;
}

7. 程序说明

1. 读入同学数和积极度。
2. 排序（方便算最大最小）。
3. 三层循环：枚举小组人数、枚举用了多少人、枚举分了多少组。
4. 用 DP 公式更新答案。
5. 记录最大值并输出。

8. 知识总结

知识点	学会了什么
分组 DP	切成一段一段
状态定义	f[j][k] 表示什么
排序	方便算最大最小
动态规划	不重复计算

9. 记忆口诀

分段问题 + 求最大值 = 动态规划 排序 + DP，帮我们抓住'最小与最大'