题目:
纸牌选手yy喜欢玩纸牌。
yy有
2n张纸牌,点数分别为
1到
2n。yy要和你玩一个游戏,这个游戏中,每个人都会分到n张卡牌。
游戏一共分为n轮,每轮你们都要出一张牌,点数大者获胜。
不自量力的yy觉得你很菜,于是每轮他都会先于你出牌,你可以根据他出的牌来做决策。
游戏开始了,你拿到了你的牌,你现在想知道,你最多能够获胜几轮?
对于
30%的数据,保证
1<=n
<=100
对于
100%的数据,保证
1<=n
<=50,000
保证数据的合法性,即你即不会拿到重复的牌,又不会拿到超出点数范围的牌。
思路: 处理出自己和对方的纸牌,并从小到大排序。 然后贪心的取一下就好了……
代码:
#include<bits/stdc++.h>
using namespace std
;
#define maxn 50000*2
#define read(x) scanf("%d",&x)
int n
;
int a
[maxn
+5],b
[maxn
+5];
bool isin
[maxn
+5];
int main() {
read(n
);
for(int i
=1;i
<=n
;i
++) read(a
[i
]),isin
[a
[i
]]=true;
for(int i
=1;i
<=2*n
;i
++) if(!isin
[i
]) b
[++b
[0]]=i
;
sort(a
+1,a
+n
+1);
int x
=1,m
=0;
for(int i
=1;i
<=n
;i
++) {
while(x
<=n
&&a
[x
]<b
[i
]) x
++;
if(x
>n
) break;
x
++,m
++;
}
printf("%d",m
);
return 0;
}