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