P6282题解

qhy_ · 2021-03-07 15:33:43 · 题解

思路

因为删除牛比较麻烦，所以我们采取从后往前添加牛的方式。

删除牛可能造成一长串连锁反应，而添加牛可以变成让占用了添加的牛的麦片的牛找麦片。

#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() {  
  ios_base::sync_with_stdio(NULL);
  cin.tie(NULL), cout.tie(NULL);
  //freopen("cereal.in", "r", stdin);
  //freopen("cereal.out", "w", stdout);
  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;
}