纸牌

纸牌

时间限制：1 sec

空间限制：512 MB

问题描述

小明有 2n 张纸牌，点数依次从 1 到 2n。小明要和你玩一个游戏，这个游戏中，每个人都会分到 n 张卡牌。游戏一共分为 n 轮，每轮你们都要出一张牌，点数小者获胜。

游戏开始了，你拿到了你的牌。你现在想知道，你最多（也就是运气最好的情况下）能够获胜几轮？

输入格式

第一行 1 个正整数 n。

第 2 行到第 n+1 行每行一个正整数 a[i]，表示你的第 i 张牌的点数。

输格式

一行一个整数表示你最多能够获胜的轮数。

样例输入

样例输

数据范围

对于 31.25% 的数据，保证 1<=n<=100

对于 100% 的数据，保证 1<=n<=50,000

保证数据的合法性，即你即不会拿到重复的牌，又不会拿到超出点数范围的牌。

代码

#include <bits/stdc++.h> using namespace std; const int N = 100005; bool exist[N];

int a[N], t;

int b[N], h; int n;

int main()

{

scanf("%d", &n);

for (int i = 1; i <= n; ++i) {

scanf("%d", &b[i]);

exist[b[i]] = 1;

}

h = 1;

t = 0;

for (int i = 1; i <= 2 * n; ++i)

if (!exist[i])

a[++t] = i;

sort(a + 1, a + n + 1);

sort(b + 1, b + n + 1);

int ans = 0;

for (int i = 1; i <= n; ++i)

if (a[i] > b[h])

++ans, ++h;

printf("%d\n", ans);

return 0;