题解：CF2060C Game of Mathletes

roumeideclown · 2025-01-20 16:14:42 · 题解

简单题。那你为什么还 Wrong answer on test 2？

这里提供一种不需要排序和双指针的解法（说实话我不太明白这题为什么会有这两个 tag）。

解法分析

此处将原题面中的序列 x 替换为 a。

我们不难发现，题意等价于求在序列 a 中最多能同时有几对整数满足它们的和为 k。

例如，在序列 1,2,3,2 中，同时存在使得 a_i+a_j=k 的二元组 (i,j) 最多有 2 组，为 (1,3) 与 (2,4)，因此答案为 2。（即第一组样例）

为什么呢？

我们称一个下标 i 与是「可匹配」的，当且仅当存在一个下标 j 使得 a_i+a_j=k，并且 i,j 不与别的下标进行匹配。

例如，对于 k=3,a=\{1,2,2\} 的情况：若我们令下标 1,2 可匹配，则此时下标 3 不是「可匹配」的；若我们令下标 1,3 可匹配，则此时下标 2 不是「可匹配」的。（讲话可能不太清楚，大家意会一下就好）

然后我们就注意到对于游戏进行到任意回合，剩余的整数数量一定为偶数，「可匹配」的下标数量也一定为偶数。

那么对于一个回合，设 Alice 选择的下标为 i，分类讨论：

• 若 i 是「可匹配」的，那么一定存在一个下标 j 满足 i \neq j 并且 a_i+a_j=k，此时 Bob 的最优策略就是选择 j，答案加一；

• 若 i 不是「可匹配」的，那么也一定存在一个下标 j 满足 i \neq j 并且 j 也不是「可匹配」的，此时 Bob 的最优策略就是选择一个不「可匹配」的下标，这样可以避免浪费掉一些「可匹配」的数，使得分数最大化。

所以题意等价于求在序列 a 中最多能同时有几对整数满足它们的和为 k。证毕。

那么如何实现呢？

我们使用一个 map 记录每个数可用（不是「可匹配」，即当前如果它没有与别的数匹配就是可用的）的数量，遍历到 a_i 时若有可用的 k-a_i，则累加答案；否则将 a_i 的数量加 1。具体看代码。

代码实现

#include<bits/stdc++.h>
// #pragma G++ optimize(2)
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=2e5+5;
int a[N];
map<int,int> mp;
void solve() {
    mp.clear(); // 清多测
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;i++) {
        if(mp[k-a[i]]>0) { // 如果有可用的 k-a[i]
            mp[k-a[i]]--; // 去掉一个
            ans++;
        }
        else mp[a[i]]++; // 无法匹配就加入可用的数
    }
    cout<<ans<<"\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}