codeforces 22D Segments

本文从WordPress迁移而来, 查看全部WordPress迁移文章

http://codeforces.com/problemset/problem/22/D

排序 贪心

题意:给一些线段,然后钉钉子,一个钉子可以穿过多个线段,要穿过所有线段,最少需要几个钉子

先将线段按左端点排序,然后逐一添加线段,并且记录在当前已经添加的线段中,哪些线段的右端点最靠左,代码中用mostright来记录这个值,如果新加入这个线段,它的左端点 > mostright,那说明必须增加一个钉子才能将这些线段全部钉起来,如果没有超过,那么这个线段还是能被之前的钉子钉住,钉子的位置就是在mostright。在当前线段的左端点 <= mostright 的时候,要用线段的右端点去尝试更新mostright;一旦出现线段左端点 > mostright,那么mostright就要重新记录,mostright就是当前这个线段的右端点。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define N 1010
#define pb push_back
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

vector<int>point;
int n,mostright,ans;
struct segment{
int l,r;
segment(){}
segment(int _l,int _r){
l = _l; r = _r;
}
bool operator < (const segment &temp)const{
return l < temp.l;
}
}a[N];

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0 ; i < n; i++){
scanf("%d%d",&a[i].l,&a[i].r);
if(a[i].l > a[i].r) swap(a[i].l,a[i].r);
}
point.clear();
sort(a,a+n);
mostright = a[0].r;
for(int i = 1; i < n; i++){
if(a[i].l <= mostright){
mostright = min(mostright,a[i].r);
}
else{
point.pb(mostright);
mostright = a[i].r;
ans++;
}
}
ans++;
point.pb(mostright);
printf("%d\n",ans);
for(int i = 0; i < point.size(); i++)
printf("%d ",point[i]);
puts("");
}
return 0;
}