---

D1. Too Many Segments (easy version)

原创 于 2023-09-07 21:53:46 发布 · 粉丝可见 · 219 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132746239

题目：

样例1：

cobol<br/>7 2<br/>11 11<br/>9 11<br/>7 8<br/>8 9<br/>7 8<br/>9 11<br/>7 9<br/>

3 1 4 7

样例2：

cobol<br/>5 1<br/>29 30<br/>30 30<br/>29 29<br/>28 30<br/>30 30<br/>

3 1 2 4

样例3：

cobol<br/>6 1<br/>2 3<br/>3 3<br/>2 3<br/>2 2<br/>2 3<br/>2 3<br/>

4 1 3 5 6

思路：

这里数据范围是 200，所以我们完全可以暴力遍历每一个点是否在该区间内，这里需要注意的是，可以通过差分的方式达到区间总和的变化，所以要学会掌握好差分。

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

struct Range
{
	int l,r;
}a[N];

int n,m;
umap<int,int>b;
umap<int,bool>r;
inline void solve()
{
	cin >> n >> m;
	for(int i = 1;i <= n;++i)
	{
		int l,r;
		cin >> l >> r;
		
		// 差分数组
		++b[l];
		--b[r + 1];
			
		a[i] = {l,r};
	}	
	
	// 差分前缀和，构造出每一个点所在位置的当前点前缀总和
	for(int i = 1;i <= 200;++i) b[i] += b[i - 1];
	
	int sz = 0;		// 删除线段数量
	
	// 开始遍历每一个点
	for(int i = 1;i <= 200;++i)
	{
		// 如果当前线段所在的点有超过了规定可重合部分 m
		// 则开始选择删除
		while(b[i] > m)
		{
			int tem = 0;	// tem 作为探头，探索哪一个需要删除的
			// 开始遍历每一个线段，寻找合适删除的线段
			for(int j = 1;j <= n;++j)
			{
				// 如果当前线段范围更广，那么应该删除，tem = j
				if(a[j].l <= i && a[j].r >= i && (!tem || a[j].r > a[tem].r) && !r[j]) tem = j;
			}
			
			// 标记已选择删除的线段
			r[tem] = true;
			
			// 累加删除线段
			++sz;
			
			// 更新区间所在点的覆盖线段数量
			for(int j = a[tem].l;j <= a[tem].r;++j) --b[j];
		}
	}
	
	// 输出答案，删除的线段
	cout << sz << endl;
	for(int i = 1;i <= 200;++i)
	{
		if(r[i]) cout << i << ' ';
	}
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：