卡牌对决

coding>C++
1.2k 词

题目描述

有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最多能赢几轮

样例输入

1
2
3
4
5
4
1
8
4
3

样例输出

1
2

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int a[50010];
int b[50010];
bool vis[100010];
int ans;
bool cmp(const int &a, const int &b){return a>b;}
int main()
{
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){scanf("%d",&b[i]);vis[b[i]] = 1;}
    int sit = 1;
    for(i=n<<1;i>=1;i--){if(!vis[i])a[sit++] = i;}
    //sort(a+1,a+1+(n>>1),cmp); // 这部分没有必要排序
    sort(a+1+(n>>1),a+1+n); 
    sort(b+1,b+1+(n>>1),cmp);
    sort(b+1+(n>>1),b+1+n);
    int r = n>>1;
    int l = 1;
    for(i=1;i<=n>>1;i++)
    {
        if(b[i] > a[l]){r--;}
        else {l++;ans++;}
    }
    l = (n>>1)+1;
    r = n;
    for(i=(n>>1)+1;i<=n;i++)
    {
        if(b[i] < a[l]){r--;}
        else {l++;ans++;}
    }
    printf("%d\n",ans);
    return 0;
}