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

· · 题解

题目传送门

Solution

考虑贪心的做法。

首先我们可以想到一个很显然的思路——找到点数 a_i 最大的卡牌 A，并用它与其余每个异色且和它相加大于 0 的数相加计入答案，同时丢弃点数较少的那张卡牌。

但是很显然，这个思路是错误的。

为什么呢？思考一种特殊情况，即与卡牌 A 的颜色 c_i 相同的卡牌极多的情况。此时我们会发现，有许多与卡牌 A 同色的卡牌的点数无法被利用到，显然无法取到最大值。

那么此时我们考虑将所有卡牌分为两类：

对于第二类卡牌，我们考虑寻找一张卡牌 B，满足与点数最大的卡牌异色，且使得它的点数最大。如此，我们可以在使用卡牌 A 操作时跳过卡牌 B，在最后用卡牌 B 与和卡牌 A 同色的卡牌时再进行卡牌 A 与 B 的操作。这样，我们就可以用卡牌 B 来利用与卡牌 A 同色的卡牌的点数了，此时我们利用了所有可利用的卡牌，显然可以取到答案最大值。

实现方面，我们可以使用排序寻找卡牌 A 和卡牌 B，再遍历整个卡牌序列，将与 A 异色的卡牌用 A 处理掉，再将与 A 同色的卡牌（包括 A）用 B 处理掉，时间复杂度 O(n\log n)。

最后需要注意的一点是，如果所有卡牌均为一色时，要特判输出 0，或将次大值设为一个极小值。

Code

#include <bits/stdc++.h>
using namespace std;
int n;
struct node{
    long long a,c=0;
}card[500005];//存储卡牌
bool cmp(node a,node b){return a.a>b.a;}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>card[i].a>>card[i].c;
    sort(card+1,card+n+1,cmp);//将卡牌按点数从大到小排序
    long long ans=0;
    long long mxn=card[1].a,mxm=0;//存储最大值，与点数最大值卡牌异色的卡牌最大值
    int l=2;
    while(card[l].c==card[1].c)//寻找与点数最大值卡牌异色的点数最大卡牌
        l++;
    if(l<=n)
        mxm=card[l].a;
    else mxm=-0x3f3f3f3f;//所有卡牌颜色相同
    for(int i=1;i<=n;i++)
    {
        if(card[i].c!=card[1].c&&i!=l)//用最大卡牌处理与其异色的卡牌（跳过mxm）
            if(card[i].a+mxn>0)
                ans+=card[i].a+mxn;
        if(card[i].c==card[1].c)//用与点数最大值卡牌异色的点数最大卡牌处理与最大卡牌同色的卡牌
            if(card[i].a+mxm>0)
                ans+=card[i].a+mxm;
    }
    cout<<ans;
    return 0;
}

这是本蒟蒻的第一篇题解，如有错误欢迎大家指正！