Too Many Segments (hard version)（贪心 + 优先队列）

题意

给出n条线段，求要使没有点被k条及以上条线段覆盖的最小删除数目，并给出方案。

分析

先按左端点排序，依次遍历，此时当前的线段之前的所有线段的左端点都小于等于当前线段，只要他们的右端点也大于等于当前线段的左端点即可。用优先队列维护这些线段的右端点的值和下标，那么队列的大小即为当前点上覆盖的线段的数目。考虑删除右端点最大的线段，这样对后续的影响最优。

但是，使用一个优先队列时只能维护最大或最小，无法满足条件。考虑使用另一个记录最大以及一个数组标记是否被删。那么，我们虽然在原本的优先队列里没删，但是我们知道该下标对应的值已经不存在了。简单维护一个差值就能知道当前优先队列的真实值的数目。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PII pair
#define mp make_pair
#define fi first
#define se second
#define ps push
#define all(a) a.begin(), a.end()
#define pb push_back
#define vec vector
#define str string
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-2;

int n, k;
struct seg {
  int id, l, r;
} p[N];
int inq[N];
int ans[N], cnt;

int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].l >> p[i].r;
    p[i].id = i;
  }
  sort(p + 1, p + 1 + n, [](const seg &a, const seg &b) {
    return a.l == b.l ? (a.r < b.r) : (a.l < b.l);
  });
  priority_queue< PII, vec, greater > pqmin;
  priority_queue< PII, vec, less > pqmax;
  int d = 0;
  for (int i = 1; i <= n; i++) {
    while (!pqmin.empty() && ( pqmin.top().fi < p[i].l || inq[pqmin.top().se] == 0) ) {
      if (inq[pqmin.top().se] == 0) d--;
      inq[pqmin.top().se] = 0;
      pqmin.pop();
    }
    inq[p[i].id] = 1;
    pqmin.ps(mp(p[i].r, p[i].id));
    pqmax.ps(mp(p[i].r, p[i].id));
    if ( (int) pqmin.size() - d > k ) {
      int del = 0;
      while (!pqmax.empty() && !inq[pqmax.top().se]) pqmax.pop();
      del = pqmax.top().se;
      ans[++cnt] = del, inq[del] = 0, d++;
    }
  }
  cout << cnt << 'n';
  for (int i = 1; i <= cnt; i++) {
    cout << ans[i] << ' ';
  }
  return 0;
}

Too Many Segments (hard version)（贪心 + 优先队列）

C/C++/C#相关栏目本月热门文章