专栏文章

区间贪心总结(8-9日作业)

rren_gao_zu
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miof40dv
此快照首次捕获于
2025/12/02 18:11
3 个月前
此快照最后确认于
2025/12/02 18:11
3 个月前
查看原文

总结

点覆盖区间问题

例题：D4327 【例6.6】整数区间（来追梦OJ）

思路：

我们先按右端点从小到大排序，然后进行遍历，就会分成两种情况：
情况一：下一个区间的左端点在这个区间的右端点的左边，此时一定有一个点可以覆盖这两个区间。
情况二：下一个区间的左端点在现在的这个区间的右边，这样两个区间独立，无公共区间，只能用两个点。

例题AC code：

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
struct node{
	int l,r;
}a[1000005];
bool cmp(node x,node y){
	return x.r<y.r;
}
int ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;

	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	int l1=a[1].l,r1=a[1].r;
	for(int i=2;i<=n;i++){
		if(r1<=a[i].l){
			r1=max(r1,a[i].r);
		}else {
			ans++;
			r1=a[i].r;
		}
	}cout<<ans;
	return 0;
}

区间和点配对问题：

例题：P2887 [USACO07NOV] Sunscreen G

思路：

先把区间按右端点从小到大排序，点按大小从小到大排序。
我们再遍历所有区间，每次遍历区间的时候遍历所有的点，如果区间和点能配上点（点在区间内），点数量减一，在把内层循环break掉。

例题AC code：

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m;
struct node{
	int l,r;
}a[1000005],b[1000005];
bool cmp(node x,node y)
{
	return x.r<y.r;	
}
bool cm1(node x,node y){
	return x.l<y.l;
}
int ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=m;i++){
		cin>>b[i].l>>b[i].r;
	}
	sort(b+1,b+m+1,cm1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[j].r>0&&b[j].l>=a[i].l&&b[j].l<=a[i].r){
				b[j].r--;
				ans++;
				break;
			}
		}
	}cout<<ans;
	return 0;
}

最大不相交区间数量问题：

选出尽量多的区间，互不重叠。

例题：D4326 【例6.5】活动选择（来追梦OJ）

思路：

  1. 按右端点从小到大排序。
  2. 维护一个目前的时间
  3. 如果此会议可以开，就开更新时间，不能就看下一个会议。

例题AC code：

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
struct node{
	int l,r;
}a[1000005];
bool cmp(node x,node y)
{
	return x.r<y.r;	
}
int ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}
	sort(a+1,a+n+1,cmp);
	int top=-1;
	for(int i=1;i<=n;i++){
		if(top<=a[i].l){
			ans++;
			top=a[i].r;
		}
	}cout<<ans;
	return 0;
}

区间覆盖问题

给出若干区间，求总共覆盖的长度。

例题：P1496 火烧赤壁

思路：

按左端点从小到大排序。
然后遍历所有区间，并维护当前区间的右端点。
如果可以，合并区间，更新右端点。
否则新开一个区间并记录上一个区间的答案。

例题AC code:

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
struct node{
	int l,r;
}a[N];
bool cmp(node x,node y){
	return x.l<y.l;
}
int n,ans;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	int l1=a[1].l,r1=a[1].r;
	for(int i=2;i<=n;i++){
		if(r1<=a[i].l){
			ans+=r1-l1;
			l1=a[i].l;
			r1=a[i].r;
		}
		else{
			r1=max(a[i].r,r1);
		}
	}cout<<ans+r1-l1;
	return 0;
}

可相交区间分组问题

例题：P10793 『SpOI - R1』Double Champions

思路：

组内区间越多，交集越小。
如果区间本身长度就小于w,则无解。
先按左端点从小到大排序。
遍历所有区间，维护交集的L和R。 当区间长度小于w,不能在一组，另开一组。

例题AC code：

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int t;
int n,w,ans=1;
struct node{
	int l,r;
}a[N];
bool cmp(node x,node y){
	if(x.l==y.l)return x.r<y.r;
	return x.l<y.l;
	
}
void solve(){
	ans=1;
	cin>>n>>w;
	bool flag=1;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
		if(a[i].r-a[i].l+1<w)flag=0;
	}
	if(w<=0){
		cout<<1<<endl;
		return;
	}
	if(!flag){
		cout<<"No\n";
		return;
	}sort(a+1,a+n+1,cmp);
	int l1=a[1].l,r1=a[1].r;
	for(int i=2;i<=n;i++){
		l1=max(l1,a[i].l);
		r1=min(r1,a[i].r);
		if(r1-l1+1<w){
			ans++;
			l1=a[i].l,r1=a[i].r;
		}
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}```

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...