「NOIAC227」random

题意：在 Alice 和 Bob 面前的是两副卡牌，每副卡牌有 $n$ 张卡片，每张卡片上有 $1$ 个数字。Alice 和 Bob 轮流随机选一张卡片，如果谁的卡片上的数更大，谁就可以获胜。现在给定这两副卡牌上的 $n$ 个数字，你需要回答是 Alice 获胜几率更大，还是 Bob 获胜几率更大。（请注意获胜几率相同的情况）

一道不知道何从下手的博弈论题。

实际上比较水，按照题目来做就对了，我们对于 Alice 和 Bob 手中的每一张卡，把对方有多少张比这张卡大的卡的数量加起来，比较 Alice 和 Bob 最后得到的数就可以得到答案。

所以先拿个桶存起来，然后在用一个数组 $sum$ ，$sum[i]$ 代表对方手中比 $i$ 大的卡有多少张，然后遍历一遍比较大小即可，注意初始化。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n;
int a[1010100],b[1010100];
int sum1[1010100],sum2[1010100];
long long A,B;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(sum1,0,sizeof(sum1));
		memset(sum2,0,sizeof(sum2));
		A=B=0;
		int x;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			a[x]++;
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			b[x]++;
		}
		for(int i=1000000;i>=0;i--)
		{
			sum1[i]=sum1[i+1]+a[i];
			sum2[i]=sum2[i+1]+b[i];
		}
		for(int i=0;i<=1000000;i++)
		{
			A+=b[i]*sum1[i+1];
			B+=a[i]*sum2[i+1];
		}
		if(A>B)
			printf("``Alice``\n");
		else if(A==B)
			printf("Tie\n");
		else
			printf("``Bob``\n");
	}
	return 0;
}