文章

16

粉丝

0

获赞

43

访问

2.7k

头像
区间移除 题解:
P5368 中国科学技术大学2025年机试题
发布于2026年3月24日 02:47
阅读数 171

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<pair<int,int>> segs;
	for(int i = 0;i < n;++i)
	{
		int a,b;
		cin >> a >> b;
		segs.push_back(make_pair(a,b));
	
	}
	sort(segs.begin(),segs.end());
	vector<pair<int,int>> ans;
	ans.push_back(segs[0]);
	int res = 0;
	for(int i = 1;i < n;++i)
	{
        // 注意这里是引用,不加引用会导致更改无法应用到原数组内
		auto& last = ans.back();
		// 如果第一个区间完全覆盖了第二个区间,代表这个大区间必须去掉,将小区间留下
		if(segs[i].first > last.first && segs[i].second < last.second)
		{
			last = segs[i];
			res++;
		}
		// 阶梯式,正常将后面覆盖的区间去掉
		else if(segs[i].first < last.second)
		{
			res++;
		}
		else
		{
			ans.push_back(segs[i]);
		}
	
	}
	cout << res << endl;
	return 0;
}

经典区间模型,区别是排序后统计区间时,如果前者区间完全覆盖了后者(前者区间头小于后者区间头,前者区间尾大于后者区间尾),那就要把前者区间去掉而保留后者,因为如果留下前面的大区间,可能会导致后面的区间仍旧有覆盖,不是最少移除区间数量(有一点贪心思想在里面)

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发