Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

有个qsort呢。。还O(n)。。╭∩╮(︶︿︶)╭∩╮

Posted by 225 at 2008-10-01 15:46:48 on Problem 1828
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator