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 |
我用的排序加贪心,各位看下有什么数据过不了,帮忙改下,谢谢指点。。#include<iostream> #include <algorithm> using namespace std; typedef struct node { long L; long R; }node; bool cmp(node &a,node &b) { if((a.L<b.L)||((a.L==b.L)&&(a.R<b.R)))return true; return false; } long i,j,k,m,a,b,n,flag,tag,num; int counter; int main() { node n[100005]; cin>>num>>m; k=0; tag=1; for(i=0; i<num;i++) { scanf("%ld%ld", &a,&b); n[k].L=a; n[k].R=b; if(a<=1 && b>=m) tag=0; k++; } counter = 0; if(!tag) cout<<1<<endl; else { flag = 0; sort(n,n+k,cmp); a=b=1; for(i=0; i<k; i++) { if(n[i].L>a) break; else { while(n[i].L<=a && i<k) { if(n[i].R>b) b = n[i].R; i++; } a=b;i--; counter++; if(b>=m) {flag=1; break;} } } if(!flag) cout<<-1<<endl; else cout<<counter<<endl; } return 1; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator