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 |
好烦啊,一次就AC了,虽然是个小菜逼,还是要装逼一下下#include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> #define MAX 100010 using namespace std; typedef struct { int a; int b; }Interval; Interval interval[MAX]; int mark[MAX]; bool cmp(Interval x, Interval y); bool cmp(Interval x, Interval y) { if(x.a != y.a) return x.a<y.a; return x.b>y.b; } int main(void) { int M, len=0, t=0; int a, b; int i, j; int begin=-1, flag; int maxb = -100001; scanf("%d", &M); while(1) { scanf("%d %d", &a, &b); if(a==0 && b==0) break; interval[len].a = a; interval[len].b = b; mark[len] = -1; len++; } sort(interval,interval+len,cmp); for(i = 0; i < len; i++) { if(interval[i].a<=0 && interval[i].b>0 && interval[i].b>maxb) { begin = i; maxb = interval[i].b; } if(interval[i].a > 0) break; } if(begin < 0) { printf("No solution\n"); return 0; } maxb = -100001; mark[t++] = begin; if(interval[begin].b >= M) { printf("1\n%d %d\n", interval[begin].a, interval[begin].b); return 0; } for(i = begin; ; i = flag) { flag = -1; for(j = i+1; interval[j].a <= interval[i].b; j++) { if(interval[j].b >= M) { mark[t++] = j; goto out; } if(interval[j].b > maxb) { maxb = interval[j].b; flag = j; } } if(flag < 0) { printf("No solution\n"); return 0; } mark[t++] = flag; } out: printf("%d\n", t); for(i = 0; i < t; i++) printf("%d %d\n", interval[mark[i]].a, interval[mark[i]].b); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator