安徽省省赛C：卡牌对决

 上一题 正确率: 27.86%27.86% 下一题 

 "

有2N张牌，它们的点数分别为1到2N。Alice拿了其中的N张，Bob拿了剩下的N张. Alice和Bob会进行N轮游戏，在每轮游戏中，Alice 和Bob 各出一张牌。出了的牌不能收回。在前N/2轮中，每轮谁的牌点数大谁就赢;在后N/2轮中，每轮谁的牌点数小谁就赢。已知Bob 每一轮会出什么牌，试求Alice 最多能赢多少轮。
 

第一行是一个整数N,
接下来N行，每行一个整数，表示Bob这轮会出什么。
2<=N <= 50000,保证N是偶数
 

输出Alice最多能赢几轮
 

4
1
8
4
3

2

这一题有点像今年预选赛的一个题目，不过预选赛的比这个简单，这个题目我还调试了一会，我还是太菜了。

之前预选赛的那一题还是队友做出来的，不过我学会了如何处理这一类的题目，直接数组贪心就可以了，不需要想多麻烦。

这一题我是把它分为前半场和后半场来算的，先算后半场，将它后半场输入的数字按照从大到小的顺序排列，然后在数组1-N*2的数组中找也没有比他小的数，有就计数变量加一，否则说明之后后半场的数都没有比他小的；然后算前半场，将它前半场输入的数从大到小排序，然后在1-N*2的数组中找是否存在比他大的数，有则计数变量加一，否则说明前半场之后的数字也没有比他大的数。

最后输出计数变量即可。

代码如下：

#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include

typedef long long ll;
typedef pairPII;
const int N = 1e6 + 50;

bool cmp(ll a, ll b)
{
    return a < b;
}
bool cmp2(ll a, ll b)
{
    return a > b;
}
ll a[N];
ll f[N];
void work()
{
    ll n,ans = 0;
    cin >> n;
    vectorv,w;
    vectorr;
    v.push_back(0);
    w.push_back(100001);
    r.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        ll x;
        cin >> x;
        if(i <= n / 2)f[x] = 10, v.push_back(x);
        else f[x] = 20,w.push_back(x);
    }
    for (int i = 1; i <= n * 2; i++)
    {
        if (f[i] == 0)r.push_back(i);
    }
    sort(v.begin(), v.end());
    sort(r.begin(), r.end());
    sort(w.begin(), w.end(),cmp2);
    int p = r.size() / 2;
    int k = 0;
    for (int i : w)
    {
        if (k == 0)
        {
            k++;
            continue;
        }
        
        while (p > 0 && (r[p] > i || f[r[p]] != 0 ))p--;
        if (p < 1)break;
        f[r[p]] = 100;
        ans++;
        p--;
    }
    p = r.size()/ 2 + 1;
    k = 0;
    for (auto i : v)
    {
        if (k == 0)
        {
            k++;
            continue;
        }

        while (p < r.size() && (r[p] < i || f[r[p]] != 0))p++;
        if (p >= r.size())break;
        f[p] = 100;
        ans++;
        p++;
    }
    cout << ans << "n";

}
int main()
{
    work();
    return 0;
}