题目大意

爱丽丝和鲍勃想出了下面这个游戏：玩家轮流玩，从爱丽丝开始。轮到一个玩家时，他选择一种颜色 ii ，这样双方都至少有一个这种颜色的弹珠。然后玩家丢弃一个颜色为 ii 的弹珠，而对手则丢弃所有颜色为 ii 的弹珠。如果没有颜色 ii 使得双方都至少有一颗该颜色的弹珠，游戏就结束了。

游戏的得分是游戏结束时爱丽丝剩余弹珠数与鲍勃剩余弹珠数之差。换句话说，游戏的得分等于 (A−B)(A-B) ，其中 AA 是爱丽丝拥有的弹珠数， BB 是游戏结束时鲍勃拥有的弹珠数。爱丽丝希望得分最大化，而鲍勃希望得分最小化。

求出得分的最大值。

解题思路

读题后不难看出这是一道博弈搜索题，数据并不大，因此我们可以直接用搜索即可。但是搜索过不了 Hard 版，因此我来讲讲贪心的思路。

双方都想要让对方的弹珠变少，可以想出第一个贪心是让双方优先选择对方弹珠数量最多的颜色减去，可以通过第一个样例，但是第二个就错了，为什么呢？因为对方的弹珠数量可能相同，此时要尽量保护好自己的弹珠数量。

细想后由此可以想出第二个贪心，每一个下标 ii 的两个权值 aia_i 和 bib_i 对于两个人的抉择都十分重要，因此我们可以定义一个结构体分别存储两个数的和与其下标，通过降序排序后便为两个人的依次抉择方案。

AC Code

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
// Problem: E1. Game with Marbles (Easy Version)
// Contest: Codeforces - Codeforces Round 916 (Div. 3)
// URL: https://codeforces.com/contest/1914/problem/E1
// Memory Limit: 256 MB
// Time Limit: 3500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long

const int N = 2e5 + 9;
const int INF = 0x3f3f3f3f;

int a[N], b[N];
bitset<N> vis;
struct Node
{
    int a, b, idx;
    bool operator < (const Node &u) const
    {
        return a + b > u.a + u.b;
    }
} f[N];


void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) cin >> b[i];
    for (int i = 1; i <= n; i ++) f[i] = {a[i], b[i], i};
    sort(f + 1, f + 1 + n);

    for (int i = 1; i <= n; i ++)
    {
        if (i & 1)
            a[f[i].idx] --, b[f[i].idx] = 0;		
        else
            a[f[i].idx] = 0, b[f[i].idx] --;
    }
    
    int suma = 0, sumb = 0;
    for (int i = 1; i <= n; i ++) suma += a[i];
    for (int i = 1; i <= n; i ++) sumb += b[i];
    
    cout << suma - sumb << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T --) solve();
    return 0;
}