P6282题解

Parat_rooper · 2021-03-07 14:04:49 · 题解

解题思路：

第一眼看到题面就想到了 30 分的暴力，复杂度为 \Theta(N^2) 。

那应该怎么优化呢？

首先我们可以模拟所有奶牛选麦片的情况，然后按照题意逐个删掉靠前的奶牛并分析情况的变化。

一只奶牛被删除时，可能会空出一种麦片可选，我们可以为所有的麦片按照编号顺序维护一个待选列表，如果当前选它的奶牛被删掉了，那么就轮到下一头奶牛选它。

同理，如果一头奶牛更换了选取的麦片，也会导致一种麦片进入待选，处理方法同上。

最后，维护麦片待选列表比较麻烦，我们可以倒序处理，每次增加一头奶牛，这样就只要维护当前选择和备选就好了。

代码如下：

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