【例54.2】 学生组队

解题思路

把能力升序排序，相邻两人组成一队，只提升较低者到较高者，费用是差值，累计第0/1、2/3……对。

正确性说明

在数轴上，若配对交叉或嵌套，改成两组相邻配对不会增加两段距离之和。反复消去非相邻配对可得相邻配对最优，费用为这些相邻差之和。

易错点

只能提升不能降低，单对最省是把小者补到大者。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x;
    sort(a.begin(), a.end());
    long long ans = 0;
    for (int i = 0; i < n; i += 2)
        ans += a[i + 1] - a[i];
    cout << ans << "\n";
    return 0;
}