贪心类区间问题

佚名 5年前 (2019-08-01) 算法 1327人围观抢沙发百度已收录

区间覆盖问题

数轴上有N个闭区间[Ai, Bi]，选择尽量少的区间覆盖一条指定线段[S, T]。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

读入时预处理，区间外的直接忽略掉，根据左端点从小到大排序一下，开始找满足左端点小于等于目前已覆盖区间的右端点、并且右端点更大的区间【绕口令吗，我在说什么......如果没找到就输出No Solution

贴

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define N 1000005
 5 inline int read(){
 6     int s=0,w=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
 9     while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
10     return s*w;
11 }
12 struct p{
13     int a,b;
14     friend bool operator < (p x,p y)
15     {
16         if(x.a==y.a) return x.b<y.b;
17         return x.a<y.a;
18     }
19 }qy[N];
20 int main()
21 {
22     int n=read(),s=read(),t=read(),cnt=0;
23     while(n--)
24     {
25         int x=read(),y=read();
26         if(x>t||y<s) continue;
27         qy[++cnt].a=x,qy[cnt].b=y;
28     }
29     sort(qy+1,qy+cnt+1);
30     int now=s,i=1,ans=0;
31     while(now<t)
32     {
33         ans++;
34         int kk=now;
35         for(;qy[i].a<=kk&&i<=cnt;i++)
36             now=max(now,qy[i].b);
37         if(now==kk&&kk<t){cout<<"No Solution\n";break;}
38     }
39     if(now>=t) cout<<ans<<endl;
40 }

View Code

同理，喷水覆盖那题预处理掉直径小于宽度的，存入直径就ok

区间不相交问题

有n项工作，每项工作分别在 si时间开始，ti时间结束。你的目标是参与尽可能多的参与工作，那么最多能参与多少项工作呢？

写得时间太久远了，但是还是能看懂的

直接贴

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 #define MAX 100005
 5 struct p{
 6     int yi,er;
 7 }qy[MAX];
 8 bool cmp(p a,p b)
 9 {
10     return a.er<b.er;
11 }
12 int main()
13 {
14     int n;
15     while(cin>>n&&n)
16     {
17         for(int i=0;i<n;i++) cin>>qy[i].yi;
18         for(int i=0;i<n;i++) cin>>qy[i].er;
19         sort(qy,qy+n,cmp);
20         int ans=0,t=0;
21         for(int i=0;i<n;i++)
22             if(t<qy[i].yi)
23             {
24                 t=qy[i].er;
25                 ans++;
26             }
27         cout<<ans<<endl;
28     }
29 }

View Code

区间选点问题

给定x轴上的n个闭区间[ai, bi]，选取尽可能少的点，使得每个闭区间至少有一个点（不同区间所含的点可以是同一个）。

排序后把第一个区间的最后一个点往下对下来，包含这个点的区间都不看，ans=1，再把点更新为出现的第一个不包含这个点的区间右端点【我好绕......。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define N 1000005
 5 inline int read(){
 6     int s=0,w=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
 9     while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
10     return s*w;
11 }
12 struct p{
13     int a,b;
14     friend bool operator < (p x,p y)
15     {
16         if(x.b==y.b) return x.a>y.a;
17         return x.b<y.b;
18     }
19 }qy[N];
20 int main()
21 {
22     int t=read();
23     for(int i=0;i<t;i++) qy[i].a=read(),qy[i].b=read();
24     sort(qy,qy+t);
25     int node=qy[0].b,ans=1;
26     for(int i=1;i<t;i++)
27         if(qy[i].a>node) node=qy[i].b,ans++;
28     cout<<ans<<endl;
29 }