题目大意：

给定\(n\)个正整数，\(a, b\)两个人轮流取，\(a\)先手

每次可以取任意多的数，直到取完，每次的得分为取的数中的最小值

\(a, b\)都会使自己的得分减去对手的得分更大，询问最后\(a\)的得分减去\(b\)的得分的大小

---

先考虑排序

排完序之后，先手一定取连续的一段

如果不取完，那么后手有更多的选择空间（可以选择大数或者带着大数选前面的区间）

设\(f[i]\)表示\(1 \sim i\)中先手取比后手取多的最大值

那么有\(f[i] = max(-f[j] + a[j + 1])\)

然后随意优化下就是\(O(n)\)啦

---

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define ll long long

#define ri register int

#define rep(io, st, ed)  for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

#define gc getchar

inline int read() {

    int p = 0, w = 1; char c = gc();

    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }

    while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();

    return p * w;

}

const int sid = 1e6 + 5;

int n;

ll f[sid];

int a[sid];

int main() {

    n = read();

    rep(i, 1, n) a[i] = read();

    sort(a + 1, a + n + 1);

    ll mx = a[1];

    rep(i, 1, n) {

        f[i] = mx;

        mx = max(mx, -f[i] + a[i + 1]);

    }

    printf("%lld\n", f[n]);

    return 0;

}