ABC088B - Card Game for Two

题意

$N$ 张牌，Alice 和 Bob 轮流取最大的牌，Alice 先手。求 Alice 总分 - Bob 总分。

思路

降序排序后 Alice 取偶数位、Bob 取奇数位，差即为答案。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-10 16:11
 * update_at: 2026-07-10 16:11
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.rbegin(), a.rend());

    int alice = 0, bob = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) alice += a[i];
        else            bob   += a[i];
    }
    cout << alice - bob << '\n';

    return 0;
}

haskell

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16{-
 Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 rainboy的学习导航网站: https://idx.roj.ac.cn
 create_at: 2026-07-10 16:16
 update_at: 2026-07-10 16:16
-}
import Data.List (sort)

main = do
    input <- getContents
    let (_:xs) = map read (words input) :: [Int]
        ys = reverse (sort xs)
        alice = sum [ y | (i,y) <- zip [0..] ys, even i ]
        bob   = sum [ y | (i,y) <- zip [0..] ys, odd  i ]
    print $ alice - bob

复杂度

时间复杂度 $O(N \log N)$ ，空间复杂度 $O(N)$ 。

总结

贪心取最大 + 交替分配。

ABC088B - Card Game for Two

目录

题意

思路

代码

复杂度

总结