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 |
Re:提供思路! 和比较容易错的情况!自己写了个快排+贪心的!附代码!!!!(仅供参考)In Reply To:提供思路! 和比较容易错的情况!自己写了个快排+贪心的!附代码!!!!(仅供参考) Posted by:2007210562 at 2009-08-11 21:06:44 #include <stdio.h> #include <algorithm> using namespace std; struct cow_t{ int s; int e; }cow[255010]; int cmp(struct cow_t a, struct cow_t b) { if(a.s == b.s) return a.e < b.e; return a.s < b.s; } int main() { int n; int t; int i, j; int start, end; int cnt = 0; scanf("%d%d", &n, &t); for(i = 0; i < n; i++) { scanf("%d%d", &cow[i].s, &cow[i].e); } sort(cow, cow+n, cmp); if(cow[0].s == 1) { j = 0; cnt = 1; start = end = cow[0].e; while(1) { for(i = j + 1; i < n; i++) { if(cow[i].s - 1 <= start && cow[i].e > end) { end = cow[i].e; j = i; } } if(end == start) break; cnt++; if(cow[j].e == t) break; start = end = cow[j].e; } if(cow[j].e == t) printf("%d\n", cnt); else printf("-1\n"); } 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