Forsaken给学生分组 题解

题目描述

Forsaken有 个学生，每个学生有一个能力值 。为了方便管理，Forsaken决定将这 个学生分成 组。

对于第 组，其"管理便利性"定义为：

求所有组的管理便利性总和的最大值：

核心结论

答案： 将学生能力值排序后，选择最大的 个元素和最小的 个元素进行配对。

关键转换： ，因为两两一组是最优策略，当 时，组数会减少。

标程实现

#include <bits/stdc++.h>
using namespace std;

int a[101010];

int main() {
    int n, k, i, j;
    cin >> n >> k;
    
    // 关键转换：k组等价于n-k组
    k = min(k, n - k);
    
    // 读入学生能力值
    for (i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 排序
    sort(a, a + n);
    
    // 贪心配对：最大的k个与最小的k个配对
    long long sum = 0;
    for (i = 0, j = n - 1; i < k; i++, j--) {
        sum += a[j] - a[i];
    }
    
    cout << sum << '\n';
}

算法解释

核心思想

要最大化管理便利性总和，我们需要让每一组的差值尽可能大。

关键观察： 两两一组是最优策略，因为：

• 当一组有超过2个学生时，我们可以将其拆分成多个两人组
• 拆分后的总贡献不会减少，且可能增加
• 因此最优解中每组最多2个学生

组数分析：

• 当 时，可以分成 组，每组2人
• 当 时，最多只能分成 组，每组2人
• 因此实际有效组数为

贪心策略

1. 排序：将学生能力值从小到大排序
2. 确定组数：，确定实际能分成多少组
3. 配对：选择最大的 个元素和最小的 个元素进行配对
4. 计算：每对贡献 的差值

算法步骤

1. 转换：k = min(k, n-k) 确定实际能分成的最大组数
2. 排序：sort(a, a+n) 将能力值排序
3. 配对：用双指针从两端向中间配对
4. 求和：累加每对的差值

关键技巧

• 双指针：i 从0开始，j 从n-1开始
• 配对策略：a[j] - a[i] 即最大k个与最小k个的差值
• 边界处理：k = min(k, n-k) 避免处理过多组

示例分析

示例：

1. 排序后：
2. k=1： 所有学生在一组
3. 差值：

一般情况：

1. 转换：
2. 排序后：
3. 配对： 和
4. 总和：

复杂度分析

• 时间复杂度： （排序的复杂度）
• 空间复杂度：