区间覆盖:
问题描述:
给定$n$个区间$[s_i,t_i]$, 选择最少的区间, 覆盖给定区间$[s,t]$
思路:
将区间按$s_i$从小到大排序, 如果第一个起点$s_1 > s$, 则无解, 否则选取$t_i$离$s$最远的区间.
此时可将指定区间视作$[t_i+1,t]$, 继续上述操作, 直至$t_i \ge t$
代码:
(poj2376) Cleaning Shifts1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53// poj2376
using namespace std;
const int Mn(25050);
struct inter //区间(intersection)
{
int s,e; //区间起点及终点
bool operator < (const inter& rhs) const //排序方式
{
return s==rhs.s ? e<rhs.e : s<rhs.s;
}
}arr[Mn];
int main()
{
int n,t;
scanf("%d %d",&n,&t);
for(int i(1);i<=n;++i) //输入
{
scanf("%d %d",&arr[i].s,&arr[i].e);
if(arr[i].s>arr[i].e)
{
int c = arr[i].e;
arr[i].e = arr[i].s;
arr[i].s = c;
}
}
sort(arr+1,arr+n+1); //排序
int p(1),ti(1); //当前查找起点(s), 当前遍历开始的区间编号
int ans(0);
while(p<=t)
{
int ed(p-1); //本次查找的终点
for(;ti<=n;++ti)
{
if(arr[ti].s<=p) //如果区间起点<=p
{
if(arr[ti].e>ed)
ed = arr[ti].e;
}
else break;
}
if(ed<p) //如果没有找到符合条件的区间
{
ans = -1;
break;
}
p = ed+1;
++ans;
}
printf("%d\n",ans);
return 0;
}
区间选点:
问题描述:
给定$n$个区间$[s_i,t_i]$, 选择最少的点, 使得每个区间都包含其中一个点.
思路:
将区间按$t_i$从小到大排序, 选择第一个区间的$t_1$, 排除已经包含点的区间, 重复此步骤直至区间全部排除完毕.
代码:
(poj1328) Radar Installation1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57// poj1328
using namespace std;
const int Mn(1050);
struct inter //同上
{
double s,e;
bool operator < (const inter& rhs) const //排序方法
{
return e==rhs.e ? s<rhs.s : e<rhs.e;
}
}arr[Mn];
inline double harclen(int y,int r) //半弦长
{
return sqrt(1ll*r*r-1ll*y*y);
}
int main()
{
int n,d;
int cnt(0);
while(~scanf("%d %d",&n,&d))
{
if(n==0 && d==0) break;
printf("Case %d: ",++cnt);
bool isans(true); //是否有解
for(int i(1);i<=n;++i)
{
int x,y;
scanf("%d %d",&x,&y);
if(y>d) isans = false;
double tmp(harclen(y,d));
arr[i].s = x-tmp; //区间起点
arr[i].e = x+tmp; //区间终点
}
if(!isans)
{
printf("-1\n");
continue;
}
sort(arr+1,arr+n+1); //排序
double p(arr[1].e); //当前选点
int ans(1);
for(int i(2);i<=n;++i)
{
if(arr[i].s<=p && arr[i].e>=p) continue; //如果该区间包含当前选点
else //否则更新p
{
++ans;
p = arr[i].e;
}
}
printf("%d\n",ans);
}
return 0;
}
选择不相交区间:
题目描述:
给定$n$个区间$[s_i,t_i]$, 选择尽量多的区间, 使得所有区间互不相交.
思路:
将区间按$t_i$从小到大排序, 选择第一个区间, 排除与之相交的区间, 再选择$t_i$最小的区间, 直至无区间剩余.
代码:
(luogu1803) 凌乱的yyy / 线段覆盖1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31// luogu1803
using namespace std;
const int Mn(1000500);
struct sect //同上(section)
{
int a,b;
bool operator <(const sect& x) //排序方式
{ return b<x.b; }
}als[Mn];
int main()
{
int n;
scanf("%d",&n);
for(int i(1);i<=n;++i)
scanf("%d %d",&als[i].a,&als[i].b);
sort(als+1,als+n+1); //排序
int ans(0),ed(0); //答案,上次终点
for(int i(1);i<=n;++i)
{
if(als[i].a>=ed) //如果不相交
{
++ans;
ed = als[i].b;
}
}
printf("%d",ans);
return 0;
}
分组不相关区间:
题目描述:
给定$n$个区间$[s_i,t_i]$, 将区间分成最少组, 使得每组内的区间互不相交.
思路:
先将区间按$s_i$从小到大排序, 记录每个组的$t_i$的最大值$aq$, 遍历每个组, 若可选则直接插入并更新$aq$, 否则新增一组. 因为按$s_i$排序后, 前面区间能够插入的组后面区间也一定能插入, 若直接插入将导致后面的区间无法插入, 则先将后面区间插入, 前面区间也一定无法插入, 组数不会变少.
换言之, 后面的区间比前面的区间选择更多, 前面区间随机选择不会挤占后面区间的选择.
然后考虑优化, 既然可以随意选择, 则不妨选择最小的$aq_i$. 使用优先队列维护$aq$即可使时间复杂度从$O(n^2)$降至$O(nlogn)$
代码:
(poj3190) Stall Reservations1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54// poj3190
using namespace std;
const int Mn(50050);
struct inter //同上
{
int s,e,no; //最后是初始编号
bool operator < (const inter& rhs) const //排序方式
{ return s<rhs.s; }
}arr[Mn];
struct pqn //优先队列时使用的数据结构(priority_queue node)
{
int n,ed; //分组编号, 分组中t_i最大值
bool operator > (const pqn& rhs) const //重载大于运算
{ return ed>rhs.ed; }
};
int ansa[Mn]; //每个区间分组
int main()
{
int n;
scanf("%d",&n);
for(int i(1);i<=n;++i)
{
scanf("%d %d",&arr[i].s,&arr[i].e);
arr[i].no = i;
}
sort(arr+1,arr+n+1); //对区间排序
priority_queue<pqn,vector<pqn>,greater<pqn> >pq; //小根堆
pq.push((pqn){1,0});
for(int i(1);i<=n;++i)
{
pqn x(pq.top()); //最小的aq_i
if(x.ed<arr[i].s) //如果可以插入
{
x.ed = arr[i].e; //更新aq_i
ansa[arr[i].no] = x.n;
pq.pop(); pq.push(x);
}
else //否则增加一组
{
x.ed = arr[i].e;
ansa[arr[i].no] = pq.size()+1;
x.n = pq.size()+1;
pq.push(x);
}
}
printf("%lu\n",pq.size());
for(int i(1);i<=n;++i)
printf("%d\n",ansa[i]);
return 0;
}