You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Alice 与 Bob 希望玩一个游戏：他们首先在黑板上写下了 $n$ 个整数 $a_1, a_2, \dots, a_n$。

然后 Alice 与 Bob 轮流行动，Alice 先手。

• 当轮到 Alice 行动时，Alice 需要选择黑板上的若干整数（至少一个），并从黑板上擦除这些整数。
• 当轮到 Bob 行动时，Bob 需要选择黑板上的一个整数，并从黑板上擦除这个数。

当一名玩家行动后，若黑板上所有数均被擦除，游戏终止。

游戏的得分被定义为 Alice 每一轮行动中所有选择的数的和。
Alice 希望最大化游戏的得分，Bob 希望最小化游戏的得分。
Alice 与 Bob 均绝顶聪明，他们会以最优的策略行动。你的任务是预测这个游戏的得分。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

输出到标准输出。

一行一个整数，表示你预测的结果。

样例输入 1

5
7 10 -5 -2 -4

样例输出 1

13

样例解释 1

最优策略的游戏流程如下：

• Alice 选择 $\{7, 10\}$
• Bob 选择 $-2$
• Alice 选择 $\{-4\}$
• Bob 选择 $-5$

游戏的得分为 $7 + 10 + (-4) = 13$。

样例输入 2

5
-6 -2 10 -7 -9

样例输出 2

1

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n \le 10^5$
• $-10^9 \le a_i \le 10^9$

具体数据范围如下表：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, a[N];
ll sum, ans = -1e18, pre[N];
signed main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	if(n == 1) {
		printf("%d", a[1]);
		return 0;
	}
	sort(a + 1, a + 1 + n);
	pre[1] = a[1];
	for (int i = 2; i <= n; ++i)
		pre[i] = pre[i - 2] + a[i];
	for (int i = n; i >= 2; --i) {
		sum += a[i];
		ans = max(ans, sum + pre[i - 2]);
	}
	printf("%lld", ans);
	return 0;
}