题目链接
solve
考试的题不开long long见祖宗了- 可以贪心，可以用dp，这里提供贪心做法
- 要求Alice先选，所以第一个必须让Alice选
废话 - 由于两人都有自己的策略，所以显然我们也可以有策略
嘻嘻 - Bob策略是选当前最大的，而Alice策略并非是选当前最大的，而是让结果最大
- 那么就是在有Bob影响下让结果最大
- 选择是随意的，那么可以排序处理
- 对于正数，对结果影响是积极的，由于Alice可以选无限个，那么就让Alice在第一轮选走所有的正数
- 对于负数，我们知道一个负数绝对值越大，对结果贡献越恶劣，那么我们就让Bob选取绝对值最大的负数即可
- 由于Alice想让结果最大，那么就要有尽可能多的负数被Bob选取，那么Alice就要选尽可能少的负数，（即只选一个）
- 如何保证Bob选的是负数中绝对值最大的数
显然，Alice选完之后，就是Bob选- 只要保证负序列是在Alice选后其中个数为奇数就行
- 若在Alice选完正数后负序列是偶数个数如何处理
- 让Alice再选一个就行了
- 如果序列全负怎么处理
- 由于Alice必须先选，还要保证选完的后序列有奇数个数，那么对于原序列的个数
-
- 若为奇数个，让Alice选第一大和第二大
- 若为偶数个，让Alice选第一大就行
- 思路不保证没锅，欢迎hack
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
long long n;
long long a[maxn];
long long ans;
int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);cin >> n;for (long long i=1;i<=n;i++) cin >> a[i];if (n == 1){cout << a[1] << endl;return 0;}sort(a+1,a+1+n);long long id=lower_bound(a+1,a+1+n,0)-a;for (long long i=id;i<=n;i++) ans+=a[i];if ((id-1) == n){ans+=a[id-1];id--;}if ((id-1)%2 == 0){ans+=a[id-1];id--;}for (long long i=id-1;i>=1;i--){if ((id-i)%2 == 0) ans+=a[i];}cout << ans << endl;return 0;
}