题解 P6179 【[USACO15DEC]High Card Wins S】
Zirnc
2020-03-06 17:05:26
[ChungZH's blog](https://chungzh.cn) · [ChungZH's portfolio](https://chungzh.cc)
------
~~比楼上大佬的方法麻烦一点~~
首先输入出牌顺序,然后排序一遍。(数组 $a$)
用一个 `flag` 数组记录一下哪些牌**不**在 Elsie 手中($a$ 中的数是 Elsie 的),也就是属于 Bessie 的牌。
把属于 Bessie 的牌计入另一个数组 $b$ 中(有序)。
然后循环一遍,如果 $b_i > a_{cur}$,那么 $cur++$。
由于 $cur$ 最开始就是 $1$(因为数组的下标都从 $1$ 开始),最后输出 $cur-1$ ,也就是 $b$ 数组中 大于 $a$ 数组其中一个数 的数 的数量即可。(~~有点绕口~~
```cpp
#include <algorithm>
#include <iostream>
using namespace std;
bool flag[100004];
int main() {
int n;
cin >> n;
int a[n + 3];
for (int i = 1; i <= n; i++) {
cin >> a[i];
flag[a[i]] = 1;
}
int b[n + 3], bidx = 1;
for (int i = 1; i <= 2 * n; i++)
if (!flag[i]) b[bidx++] = i;
sort(a + 1, a + n + 1);
int cur = 1;
for (int i = 1; i <= n; i++) {
if (b[i] > a[cur]) {
cur++;
}
}
cout << cur - 1 << endl;
return 0;
}
```