Chess Match – Gym 100971L – 贪心

来源: Chess Match – Gym 100971L – Virtual Judge

题目大意:给出两只队伍成员的能力值,能力值大的一定可以战胜能力值小的,但是出场顺序不定,问是第一支队伍必赢还是第二支队伍必赢还是都有可能赢还是必平。
解题思路:用两个指针遍历排序后的a,b数组,让a[i]去和b中没有选择过的最小的打,这样是对a最有利的,记录最多a可以赢的局数,同理反过来可以记录当对b最有利时b最多可以赢的局数。
如果局数大于n/2,那么就是说可以赢,如果两种情况都能赢的话说明是Bboth,否则只可能是first,secend,如果任意一方最优情况下也不能赢的话就是NONE。
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int a[200020],b[200020];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    int j=1;
    int numa=0,numb=0;
    for(int i=1;i<=n;i++)
    {
        if(j<=n&&b[j]<a[i])
        {
            numa++;
            j++;
        }
    }
    j=1;
    for(int i=1;i<=n;i++)
    {
        if(j<=n&&a[j]<b[i])
        {
            j++;
            numb++;
        }
    }
    if(numb>n/2&&numa>n/2)
    {
        cout<<"Both"<<endl;
    }
    else if(numa>n/2)
    {
        cout<<"First"<<endl;
    }
    else if(numb>n/2)
    {
        cout<<"Second"<<endl;
    }
    else cout<<"None"<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注