AT2645题解

Polaris_Australis_ · 2022-05-19 22:08:53 · 题解

题目传送门

做法

本题有 hall 定理 + 线段树做法，详见大佬的博客

思路：让所有的人先尽可能坐在左面，坐不下的做右面，然后实在坐不了的就填椅子。

实现：

• 把所有人按照以 l 为第一关键字，r 为第二关键字排序，ex 数组初值均为 -1，每次选择一个人，看他前面能坐的椅子是否坐满，如果没满，就直接做当前所剩椅子中最左面的一个，并插入到优先队列中表示可以被替换，如果已经满了，就要从所有可以被替换的这些人里找第二关键字最小的一个替换（这样可以给后面留足够大的空间让更多人坐），这样的话自己就坐在了。
• 统计答案：考虑 ex_i 数组后缀和的含义即为从 i 到 n 有多少个人没有椅子，且这些人一定要坐在坐标大于等于 i 的位置，这样后缀和中最大的即为答案。

思路来自大佬 @tjn1234

代码

#include <bits/stdc++.h>
using namespace std;
namespace Std {
int n, m, now, ex[200010], ans, res;
struct node {
  int l, r;
  friend bool operator<(const node& a, const node& b) {
    return (a.l == b.l) ? a.r < b.r : a.l < b.l;
  }
} t[200010];
struct num {
  int sum;
  friend bool operator<(const num& a, const num& b) { return a.sum > b.sum; }
};
priority_queue<num> q;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &t[i].l, &t[i].r);
  }
  sort(t + 1, t + n + 1);
  for (int i = 1; i <= m; i++) ex[i] = -1;
  for (int i = 1; i <= n; i++) {
    if (t[i].l == 0) {
      ex[t[i].r]++;
    } else if (t[i].l == now) {
      num u = q.top();
      q.pop();
      ex[u.sum]++;
      u.sum = t[i].r;
      q.push(u);
    } else {
      ex[++now]++;
      num u;
      u.sum = t[i].r;
      q.push(u);
    }
  }
  for (int i = m + 1; i >= 0; i--) {
    res += ex[i];
    ans = max(ans, res);
  }
  printf("%d\n", ans);
  return 0;
}
}  // namespace Std
int main() { return Std::main(); }