题解 P6179 【[USACO15DEC]High Card Wins S】

· · 题解

ChungZH's blog · ChungZH's portfolio

比楼上大佬的方法麻烦一点

首先输入出牌顺序，然后排序一遍。（数组 a）

用一个 flag 数组记录一下哪些牌不在 Elsie 手中（a 中的数是 Elsie 的），也就是属于 Bessie 的牌。

把属于 Bessie 的牌计入另一个数组 b 中（有序）。

然后循环一遍，如果 b_i > a_{cur}，那么 cur++。

由于 cur 最开始就是 1（因为数组的下标都从 1 开始），最后输出 cur-1 ，也就是 b 数组中 大于 a 数组其中一个数 的数 的数量即可。（有点绕口

#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;
}