| ||||||||||
| 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