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 |
有个qsort呢。。还O(n)。。╭∩╮(︶︿︶)╭∩╮In Reply To:受不了了, O(n)的算法都超时 Posted by:zyz at 2007-05-06 21:12:34 > #include<iostream> > using namespace std; > > typedef struct{ > int x; > int y; > }node; > > node nodes[50002]; > //int use[50002]; > > int cmp(const void *pl, const void *pr){ > node *p1 = (node*)pl; > node *p2 = (node*)pr; > if(p1->x == p2->x) > return p1->y - p2->y; > return p1->x - p2->x; > } > > int main(){ > int num; > while(cin>>num && num){ > for(int i=0;i<num;i++) > cin>>nodes[i].x>>nodes[i].y; > qsort(nodes, num, sizeof(node), &cmp); > // memset(use, 0, num*sizeof(int)); > int total=1; > int max=nodes[num-1].y; > for(int i=num-2;i>=0;i--){ > if(max<nodes[i].y){ > max=nodes[i].y; > total++; > } > } > cout<<total<<endl; > } > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator