Codeforces Round #693(div3.D)博弈_codeforces round #693 (div. 3)

题意

Alice取偶数加分取奇数不加分，Bob反之。

思路

最优的策略就是在本回合获得最大的利益，也就是要在获取分数与防止对方下次获得多的分数，不难想到，只需要判断自己当前回合能获得最大分数是否大于对方下次获得的最大分数，如果是，就拿能给自己加最多分的那个数，反之拿掉对手的最大数。

#include<bits/stdc++.h>
using namespace std;
long long a[200100];
long long o[200100],j[200100]; 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int o1=0,j1=0;
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			if(a[i]%2==1)
			{
				j[j1]=a[i];
				j1++;
			}
			else
			{
				o[o1]=a[i];
				o1++;
			}
		}
		sort(o,o+o1);
		sort(j,j+j1);
		long long ali=0,bob=0;
		int flag=0;
		while(o1>0||j1>0)
		{
			if(o[o1-1]>j[j1-1])
			{
				if(flag==0)
				{
					flag=1;
					ali+=o[o1-1];
					o1--;
				}
				else
				{
					flag=0;
					o1--;
				}
			}
			else if(o[o1-1]<j[j1-1])
			{
				if(flag==0)
				{
					flag=1;
					j1--;
				}
				else
				{
					flag=0;
					bob+=j[j1-1];
					j1--;
				}
			}
		}
		if(ali>bob)
		printf("Alice\n");
		else if(ali<bob)
		printf("Bob\n");
		else
		{
			printf("Tie\n");
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72