题解：P11782 [JOIGST 2024] 卡牌游戏 / Card Game 3

CaYi · 2025-08-15 20:22:05 · 题解

题面

P11782

解析

首先答案肯定大于等于 0，因为初始就是 0，可以不行动。

一个比较显而易见的贪心思想，既然可以多次累加某张卡牌的 a，当然要让这张卡牌的 a 尽量大。不妨先将所有卡牌依照 a 的大小排序，用最大的那一张匹配剩余卡牌中与其颜色不同的，若二者 a 之和大于 0，累加进答案中。

那么剩下的与最大 a 卡牌同色的怎么办？我们可以取其异色的最大 a 卡牌（颜色与其不一样的卡牌里面 a 最大的，下文称作最大 a 异色卡牌）和剩余卡牌匹配，贡献大于 0 的累加进答案（所以这一张卡在上一个步骤，也就是上一个自然段里提到的操作，应该被跳过，详情见代码）。

最后判断最大 a 卡牌与最大 a 异色卡牌二者 a 之和是否大于 0，若大于，则累加进答案。

扫了两遍序列，排了一次序，复杂度 \operatorname{O}(n \log n)。

一个小坑，若全场颜色只有一种，答案是 0，特判一下即可（我因为这个东西死了一发WA），一道水题就被切掉了。

Code Time

/*
code by : CaYi
*/
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
//using i128 = __int128;

const int N = 5e5 + 6;

struct card {
    int a, c;
};

int n;
card r[N];
i64 cnt[N];
i64 ma, sea, ans;

int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);

    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        std::cin >> r[i].a >> r[i].c;
    }

    std::sort(r + 1, r + 1 + n, [] (card a, card b) {
        return a.a > b.a;
    });

    int mac = r[1].c;//记录最大 a 卡牌的颜色

    int pos = 2;
    while (r[pos].c == mac) {pos++;}//第一个异色的就是最大 a 异色卡
    sea = r[pos].a;
    if (pos == n + 1) {//特判颜色全部一样
        std::cout << 0 << '\n';
        return 0;
    }

    for (int i = 2; i <= n; i++) {
        if (r[i].c != mac && i != pos) {//不能与最大 a 异色卡获取分数，因为这俩是最后计算的
            if (r[i].a + r[1].a >= 0) {
                ans += r[i].a + r[1].a;
            }
        }
    }

    for (int i = 2; i <= n; i++) {//这里i = 2隐性地跳过了最大 a 卡牌与最大 a 异色卡的分数计算，因为最大 a 卡牌在 i = 1 的位置
        if (r[i].c == mac) {
            if (r[i].a + sea >= 0) {
                ans += r[i].a + sea;
            }
        }
    }

    if (r[1].a + sea > 0) {
        std::cout << ans + sea + r[1].a << '\n';
        return 0;
    }

    std::cout << ans << '\n';

    return 0;
}