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 |
本题本人是用排序加贪心,提供一组数据,我就是在这上面wa了好几次!!!4 10 1 4 6 8 8 9 9 10 输出为 -1 再给一下AC代码吧,供大家参考 #include<iostream> #include<algorithm> #define MAX 25001 using namespace std; struct Cow { int start; int end; }; int comp(struct Cow a, struct Cow b) { return (a.start < b.start) || (a.start == b.start && a.end > b.end); } Cow cows[MAX]; int main() { int nN, nT, i, temp, ret, max, flag; while(2 == scanf("%d%d", &nN, &nT)) { ret = 0; for(i = 0; i < nN; i++) scanf("%d%d", &cows[i].start, &cows[i].end); sort(cows, cows+nN, comp); if(cows[0].start != 1) { printf("-1\n"); continue; } temp = cows[0].end; if(temp == nT) { printf("1\n"); continue; } ret++; i = 1; while(i < nN) { flag = 0; max = cows[i].start; while(cows[i].start <= temp+1) { flag = 1; if(max < cows[i].end) max = cows[i].end; i++; } if(flag == 0) break; ret++; if(max == nT) { printf("%d\n", ret); break; } temp = max; } if(flag == 0 || max < nT) printf("-1\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator