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 |
2376为什么会TLE呢,o(n)的算法难道不行么?????????? 求助!!!!!!!!!!!!! 求助!!!!!!!!!!!!! 求助!!!!!!!!!!!!! //TLE code: #include <iostream> #include <algorithm> #include <stdio.h> #include <stdlib.h> using namespace std; struct node { int x; int y; }; node cnt[25010]; int N,E; bool cmp(node a,node b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x; } int main() { while (scanf("%d %d",&N,&E) != EOF) { int minn = 100000000; int maxn = 0; for (int i = 0; i < N; ++i) { scanf("%d %d",&cnt[i].x,&cnt[i].y); minn = min(minn,cnt[i].x); maxn = max(maxn,cnt[i].y); } if (minn > 1 || maxn < E) printf("-1\n"); else { sort(cnt,cnt + N,cmp); if (cnt[0].x != 1) { printf("-1\n"); } if (cnt[0].y >= E) { printf("1\n"); } int i = 1; int s = cnt[0].x; int e = cnt[0].y; int sum = 1; for (; i < N; ++i) { //cout << i << " " << s << " " << e << endl; if (e >= E) break; if (s == cnt[i].x) { e = cnt[i].y; continue; } if (cnt[i].x >= s && cnt[i].x <= e) { if (cnt[i].y >= E) { s = cnt[i].x; e = cnt[i].y; sum++; break; } else continue; } else { if (e + 1 == cnt[i].x) { s = cnt[i].x; e = cnt[i].y ; } else { s = cnt[i - 1].x; e = cnt[i - 1].y; i -= 1; }; sum++; } } //cout << s << " " << E << endl; if (e >= E) printf("%d\n",sum); else 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