专栏文章

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

CCaYi
P11782题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miobe73i
此快照首次捕获于
2025/12/02 16:26
3 个月前
此快照最后确认于
2025/12/02 16:26
3 个月前
查看原文

题面

P11782

解析

首先答案肯定大于等于 00，因为初始就是 00，可以不行动。
一个比较显而易见的贪心思想，既然可以多次累加某张卡牌的 aa，当然要让这张卡牌的 aa 尽量大。不妨先将所有卡牌依照 aa 的大小排序，用最大的那一张匹配剩余卡牌中与其颜色不同的，若二者 aa 之和大于 00，累加进答案中。
那么剩下的与最大 aa 卡牌同色的怎么办？我们可以取其异色的最大 aa 卡牌（颜色与其不一样的卡牌里面 aa 最大的，下文称作最大 aa 异色卡牌）和剩余卡牌匹配，贡献大于 00 的累加进答案（所以这一张卡在上一个步骤，也就是上一个自然段里提到的操作，应该被跳过，详情见代码）。
最后判断最大 aa 卡牌与最大 aa 异色卡牌二者 aa 之和是否大于 00，若大于，则累加进答案。
扫了两遍序列，排了一次序，复杂度 O⁡(nlog⁡n)\operatorname{O}(n \log n)。
一个小坑，若全场颜色只有一种，答案是 00，特判一下即可（我因为这个东西死了一发WA），一道水题就被切掉了。

Code Time

CPP
/*
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;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...