专栏文章

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

KKLaneX
P11782题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min5nne9
此快照首次捕获于
2025/12/01 20:58
3 个月前
此快照最后确认于
2025/12/01 20:58
3 个月前
查看原文
原题链接 可能更好的阅读体验

切入

由于 n≤5×105n\le5\times10^5，直接一眼贪心。
首先要找出所有牌中的最大值 maxn1maxn1 以及其对应的颜色 col1col1，用来匹配与 col1col1 不同颜色的牌，只要有 ai+maxn1>0a_i+maxn1>0，就可以添加至 ansans 的贡献中。
而对于与 col1col1 同色的卡牌来说，则需要找出一个与 col1col1 不同色的卡牌中的最大值，与同色的卡牌相匹配。 代码实现方面，我们可以用结构体存储点数和颜色，然后对它快排，找出最大值与不同色的次大值，之后一一匹配即可。
记得要给次大值的 maxn2maxn2 设定一个极小值，以特判当所有颜色都为同一种颜色的情况。
时间复杂度为 O(nlog⁡n)O(n\log n)。

优化

注意到我们的算法复杂度的瓶颈在于快排，但我们其实并不需要对所有的数据进行排序，只需要找到最大值和不同色的次大值就可以了，只需两个 for 循环即可实现（其实一个就够了）。
要记得统计最大值所对应的 idxidx，以防重复贡献。
优化后的时间复杂度为 O(n)O(n)。
其余细节详见代码。
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define endll " "
#define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define pii pair<int,int>
#define lowbit(x) x&-x
#define pb push_back
#define eb emplace_back
#define it inline int 
#define iv inline void
#define ib inline bool
using namespace std;
const int MAXN=500050;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
it gcd(int x,int y) {return y==0?x:gcd(y,x%y);}
it lcm(int x,int y) {return x/gcd(x,y)*y;}
it max(int x,int y) {return x>y?x:y;}
it min(int x,int y) {return x<y?x:y;}
it ksm(int x,int m,int mod)
{
	int res=1,bas=x%mod;
	while(m)
	{
		if(m&1)
			res=(res*bas)%mod;
		bas=(bas*bas)%mod;
		m >>= 1;
	}
	return res%mod;
}
int n,m,l,r,u,v,w,cnt,tot,ans,head[MAXN],maxn1,maxn2=-INF,col1,col2,idx;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
struct lane
{
	int val,col;
}t[MAXN];
signed main()
{
	//fre("");
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> t[i].val >> t[i].col;
	for(int i=1;i<=n;i++)
	{
		maxn1=max(maxn1,t[i].val);
		if(maxn1==t[i].val)
        {
			col1=t[i].col;
            idx=i;
        }
	}
	for(int i=1;i<=n;i++)
	{
		if(t[i].col!=col1)
		{
			maxn2=max(maxn2,t[i].val);
			if(maxn2==t[i].val)
				col2=t[i].col;
		}
	}
	if(maxn2==-INF)
	{
		cout<<ans;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(t[i].col!=col1 && t[i].val+maxn1>0)  //与最大值匹配
			ans+=t[i].val+maxn1;
		if(t[i].col==col1 && t[i].val+maxn2>0 && idx!=i)  //次大值不同色与最大值的颜色相同的匹配,不计算遇到最大值时的贡献,避免重复贡献
			ans+=t[i].val+maxn2;
	}
	cout<<ans;
	return 0;
}

评论

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

正在加载评论...