Description：

$N$ 个正整数，每次可以取任意多个数，每次获得的得分为取的数中的最小值， $A$ 和 $B$ 的策略都是尽可能使得自己的得分减去对手的得分更大。求最终 $A$ 的得分减去 $B$ 的得分。

$1\le n \le 1000000$

Solution：

所有人都一定是按从大到小的顺序每次选连续的一段，所以先按从小到大排序，设 $f[i]$ 表示到了 $i$ 差最大是多少，转移为 $f[i]=\max(a[j]-f[j-1])(1\le j<i)$ ，这样转移是 $O(n^2)$ 的，但是发现可以用前缀最大值优化，转移实际上是 $f[i]=\max(f[i-1],a[i]-f[i-1])$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN];

int f[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

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

	f[0] = 0;

	for(int i = 1;i <= n;++i)

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

	cout << f[n] << endl;

	return 0;

}