题解 P4816 【[USACO15DEC]高低卡(金)High Card Low Card (Gold)】

· · 题解

思路：贪心

赤裸裸的贪心

把读入的数据分成1~n/2，n/2+1~n两份，排序，用剩下的数（也就是Bessie的牌）最大的对第一份最大的数，依次减小，最小的对第二份最小的，依次增大

上代码咯
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[25001],c[25001],b[100001];||a存前半部分，c存后半部分，b记录是谁的牌
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n/2;i++)
    {
        cin>>a[i];
        b[a[i]]=1;
    }
    for(int i=1;i<=n/2;i++)
    {
        cin>>c[i];
        b[c[i]]=1;
    }
    sort(a+1,a+1+n/2);
    sort(c+1,c+1+n/2);||排序，方便下面贪心
    int j=2*n;
    for(int i=n/2;i>=1;i--)||从大到小枚举前半部分
    {
        while(b[j]&&j>=1)||找到Bessie未用的最大的牌
            j--;
        if(j<a[i])||最大的也比这张牌小，无解
            continue;
        else
            b[j]=1,ans++;       
    }
    j=1;    
    for(int i=1;i<=n/2;i++)
    {   
        while(b[j]&&j<=2*n)||找到Bessie未用的最小的牌
            j++;
        if(j>c[i])||最小的也比这张牌大，无解
            continue;
        else
            b[j]=1,ans++;
    }
    cout<<ans;
    return 0;
}

安利一发博客liyilin2004的博客 欢迎来拜访⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄