题解 P6282 【[USACO20OPEN] Cereal S】

jiang_cheng · 2021-03-07 16:03:48 · 题解

解题思路：

暴力是很容易想到的，就是每次模拟一遍奶牛选麦片就行了。但这样做复杂度太高，所以得换种方法。

想一想，减少一头奶牛会怎么样：首先，如果它选择了麦片，它就会空出它选择的麦片。否则，也不会影响其他奶牛。但这样做有点难模拟，所以我们可以倒着来，考虑从后往前增加奶牛。

如果增加一头奶牛：新奶牛它的优先级是目前最高的，所以它就可以拿自己最喜欢的麦片，就有可能与其他奶牛发生冲突，这时我们循环处理冲突，让其他奶牛选第二喜欢的麦片，如果它第二喜欢的麦片也没了，它就不选，后面的奶牛选择的麦片不会改变，冲突也就没有了。

附上代码：

#include <iostream>

using namespace std;

const int kMaxN = 1e5 + 1;

struct E {
  int c[2], p;  // 喜欢的麦片编号、当前选择的下标
} e[kMaxN];
int a[kMaxN], b[kMaxN];  // 答案、选择每种麦片的奶牛
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> e[i].c[0] >> e[i].c[1];
  }
  e[0].p = 2;                            // 初始化判断边界
  for (int i = n, s = 0; i >= 1; i--) {  // 倒序加入奶牛
    for (int j = i; e[j].p < 2;) {       // 不断解决冲突
      int x = e[j].c[e[j].p++];          // 当前奶牛要选的麦片
      if (j < b[x]) {                    // 当前奶牛优先级更高
        swap(b[x], j);                   // 切换选择，继续处理换掉的奶牛
      } else if (!b[x]) {                // 当前麦片未被选择
        b[x] = j;
        s++;  // 增加答案
        break;
      }
    }
    a[i] = s;  // 记录答案
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << endl;
  }
  return 0;
}