CF2060C Game of Mathletes 题解

每一轮，Alice 先取数，Bob 后取，当两人所取的和为 $k$ 时，加一分，Alice 希望的分最小，Bob 希望最大，两人按最优方式操作，求最终得分。

当两个数的和等于 $k$ 时，这一对数就是可得分的，可以发现，Alice 的取数方法与结果无关，而对于 Alice 的数，当这个数可得分时，Bob 会取出对应的一个数使之得分，否则 Bob 则取出一个不可得分的数，没有得分。

于是，答案就是可得分数组合的数量（当然每个数只能用一次）。

于是就有了一个用映射维护的 $10$ 行写法，注意 tot 不要改为数组，否则可能会访问负数下标。

1
2
3
4
5
6
7
8
9
10
11
12

void solve(){
	int n,k,x,ans=0;
	tot.clear();
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		tot[x]++;
	}
	for(auto i:tot)
		ans+=min(tot[i.first],tot[k-i.first]);
	printf("%lld\n",ans/2);
}//是不是比官方题解简单多了