P4816 High Card Low Card G题解

· · 题解

P4816 High Card Low Card G题解

思想：贪心

题意简述

给你 n 张点数从 1 到 2 \times n 的纸牌，让你用未出现过的、点数在 1 到 2 \times n 之间的纸牌与指定出牌顺序的对手玩牌。玩的过程分为两个部分，前半个部分出的点数大者获胜，后半个部分出的点数小者获胜。求最多获胜局数。

解题思路

可以发现此题是类似于一个田忌赛马的游戏，尽量出比对面的牌略大的牌，若找不到则出最小的牌。进一步思考，由于前半局需要出牌点数尽可能大，后半句需要尽可能小，故可以贪心地考虑把玩家的牌按照大小分成前后两个相同的部分，分别用于玩一、二两个部分。由于两个部分是互相独立的，所以可以把对手的纸牌也分成两部分。

把对手的纸牌排序，第一部分的牌从大到小排序，第二部分的牌从小到大排序。容易可以用一个双端队列维护自己的牌，第一部分时查看是否可以让队首的牌战胜对手当前的牌，若可以，则该牌从队首出队；第二部分时从队尾出队

由于玩家的牌和对手的牌总数相同，所以，在把此问题转化为田忌赛马后，可以不用考虑当无法与对手的牌抗衡时出小牌的情况，直接跳过该牌即可。

在处理方面，由于出现的数字上下界比较小，可以使用桶来记录牌是否出现，又由于牌的点数不会重复，考虑到常数的问题，笔者使用了 bitset 充当桶。用桶记录有另一个好处，就是取出后的序列自动有序，不需要重新进行排序。

代码

#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
const int N=50005;
int a1[N],n,a2[N],b[N];
bitset<N<<1> t;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n>>1;i++)
        scanf("%d",&a1[i]),t[a1[i]]=1;
    for(int i=1;i<=n>>1;i++)
        scanf("%d",&a2[i]),t[a2[i]]=1;
    int bn=0;
    for(int i=1;i<=n<<1;i++)
    if(!t[i])
    b[++bn]=i;
    sort(a1+1,a1+(n>>1)+1,cmp);
    sort(a2+1,a2+(n>>1)+1);
    int st=1,tl=bn,ans=0;
    for(int i=1;i<=(n>>1);i++)
        if(b[tl]>a1[i])
            tl--,ans++;
    for(int i=1;i<=(n>>1);i++)
        if(b[st]<a2[i])
            st++,ans++;
    printf("%d\n",ans);
}

如果觉得有帮助，点一个免费的赞可以么？