题解 | #Forsaken给学生分组#

根据题面，我们的目标是最大化这个总和：

• 
• 等同于：

那么问题就变成了： 从 个学生中，选出 个作为各组的最大值， 个作为各组的最小值，使得最大值们的总和与最小值们的总和之差最大。

1. 如何让 最大？
   • 很简单，我们从排好序的数组中，选择最大的 个数 作为这 个组的 。
2. 如何让 最小？
   • 同样，我们选择最小的 个数 作为这 个组的 。

最后把就是结果了

附AC代码

#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
#define int long long
using namespace std;

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (auto &x : v)
        is >> x;
    return is;
}

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    cin >> v;
    sort(all(v));
    int ans = 0;
    for (int i = n - k; i < n; ++i)
    {
        ans += v[i];
    }
    for (int i = 0; i < k; ++i)
    {
        ans -= v[i];
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

简言之，为最大化总管理方便度 ，我们将目标重构为最大化 。因此，最优策略是选择数组中最大的 个数作为 组的 值，并选择数组中最小的 个数作为 组的 值，答案即为这两组数各自求和后的差值。