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 |
sort + 贪心,直接附代码#include <iostream> #include <algorithm> #include <cstdio> using namespace std; struct inter{ int s, g; inter(int s = 0, int g = 0): s(s), g(g) {} bool operator < (const inter& b) const { if(this->s != b.s) return this->s < b.s; else return this->g < b.g; } }; const int maxn = 25000+5; const int INF = 1e8; int N, T; inter itv[maxn]; int tanxin() { int ans = 0, g; int left = upper_bound(itv, itv+N, inter(1, INF)) - itv; int right; if(left == 0) return -1; else { left--; g = itv[left].g; ans++; } while(g < T) { right = upper_bound(itv+left, itv+N, inter(g+1, INF)) - itv; g = 0; int maxpos = -1; for(int i = left+1; i<right; i++) { if(itv[i].g > g) { maxpos = i; g = itv[i].g; } } if(maxpos == -1) return -1; else { left = maxpos; ans++; } } return ans; } int main() { scanf("%d %d", &N, &T); for(int i = 0; i<N; i++) scanf("%d %d", &itv[i].s, &itv[i].g); sort(itv, itv+N); int ans = tanxin(); printf("%d\n", ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator