| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大家注意特判这个题的代码很好写,排序然后贪心就好了。但是有一些特判需要注意。
如果n=1,如数据:1 5 1 5 就需要加一条特判直接输出 1 如果跑贪心就跪了。
其次排序结果如果第一个段开头不是1,可以直接输出 -1。
附个人代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 25100;
struct Segment{
int l, r;
}segment[MAXN];
int n, t, tail, time, MAX;
int cmp(Segment a, Segment b){ return a.l < b.l || a.l == b.l && a.r > b.r;}
int main(){
memset(segment, 0, sizeof(segment));
scanf("%d%d", &n, &t);
for(int i = 1; i <= n; i++) scanf("%d%d", &segment[i].l, &segment[i].r);
sort(segment + 1, segment + n + 1, cmp);
tail = segment[1].r, time++;
if(segment[1].l != 1) { printf("-1"); return 0;}
if(segment[1].l == 1 && segment[1].r == t) { printf("1"); return 0;}
for(int i = 1; i <= n; i++){
if(segment[i].l <= tail + 1) MAX = max(MAX, segment[i].r);
else{
if(tail == MAX) { printf("-1"); return 0;}
tail = MAX, i--, time++;
}
if(MAX == t) { tail = MAX; time++; break;}
}
if(tail != t) { printf("-1"); return 0;}
printf("%d", time);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator