本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-20 19:30:15

CF1249D1 Too Many Segments (easy version) 题解

原题链接

题目描述

给定 $n$ 个区间以及一个数字 $k$，每对 $l,r$ 覆盖的区间会 $+1$，求至少要删除多少个区间才能使得每个位置的值都不超过 $k$，输出删除的最小个数 $m$ 及删除的方案。

做法

看到数据范围 $n \le200$，我们可以接受 $O(n^3)$ 的做法。

首先我们处理区间加减，这一点可以使用差分数组实现，我们在需要修改开头 $l$ 位置 $+1$，在结尾 $r + 1$ 位置 $-1$。因为可以接受 $O(n^3)$，所以也可以直接暴力修改。

我们直接枚举每个位置，看每个位置上该点是否符合条件，如果不符合条件，那么我们优先删除包含当前点，未被删除，右端点尽可能大的区间。

为什么要右端点尽可能大呢？

我们考虑当前枚举到 $i$ 那么它前面的所有点一定都符合条件，所以我们应该让删除的区间尽可能包含更多后面的点，显然这样更优。于是我们直接把所有区间按照右端点排序，然后暴力枚举判断即可。

这样外层枚举位置 $i$，内层枚举区间并暴力删除，这样最劣的复杂度是 $O(n^3)$ 的，可以通过。

同时我们可以使用差分优化掉暴力修改的一维，时间复杂度为 $O(n^2)$。

但是显然在加强版中还是无法通过，所以还可以继续优化下去，我们分析可以知道代码主要的复杂度在枚举每一个区间上面。我们考虑怎么样避免枚举的复杂度。

这时候就需要使用数据结构及一些技巧了。

我们考虑既然从左到右判断每个点，那么当我们把整个区间都按照 $l$ 值从左到右排序，那么每次这个点只会使用到左端点小于它的区间。

同时我们要使得右端点尽可能的大，所以我们可以维护出一个优先队列。我们在优先队列中按照区间的右端点排序，这样每次取出堆顶都是满足条件的右端点最大的区间，我们再差分删除这个区间即可。

这样外层枚举位置为 $O(V)$（值域），内层优先队列为 $O(\log n)$。由于值域 $V$ 和 $n$ 同阶，所以复杂度为 $O(n \log n)$，足够通过强化版本。

AC Code

#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;
struct note{
	int l,r,id;
}se[maxn];

bool cmp(note a,note b)
{
	return a.l < b.l;
}

struct ccmp{
	inline int operator () (const note &a,const note &b) const
	{
		return a.r < b.r;
	}
};

int d[maxn];
priority_queue<note,vector<note>,ccmp> q;
vector<int> ans;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> se[i].l >> se[i].r;
		se[i].id = i;
		d[se[i].l]++;
		d[se[i].r + 1]--;
	}
	sort(se + 1,se + n + 1,cmp);
	int now = 1;
	int cnt = 0;
	for(int i = 1;i <= 2e5;i++)
	{
		d[i] += d[i - 1];
		while(now <= n && se[now].l <= i)
		{
			q.push(se[now]);
			now++;
		}
		while(d[i] > k && !q.empty())
		{
			note p = q.top();
			q.pop();
			d[i]--;
			d[p.r + 1]++;
			cnt++;
			ans.push_back(p.id);
		}
	}
	cout << cnt << endl;
	for(int i = 0;i < cnt;i++) 
	{
		cout << ans[i] << " ";
	}
	return 0;
}

如果想要看强化（数据范围较大）版本，请移步CF1249D2 Too Many Segments (easy version)。

感谢阅读，希望对你有所帮助。