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

都排序了,还O(n)……o(╯□╰)o

Posted by jyd at 2009-10-07 09:44:37 on Problem 1828
In Reply To:这道题还听有人说是dp,原来一道超级水题。 Posted by:ccsu2008021220 at 2009-10-07 01:17:10
> 做题之前听说是dp,怀着dp的心情去解,后来越来越发现不对劲,值感觉这道题没学算法也能AC掉,就是一个简单的排序在加选取策略就a了,复杂度也就O(n).
> 贴代码:
> #include<iostream>
> #include<algorithm>
> using namespace std;
> struct lct{
>     int x,y;
> }a[50001];
> struct pt_cmp
> {
>    bool operator()(const lct &a,const lct &b)const 
>    {
>       if ( a.x == b.x ) return a.y < b.y;
>       return a.x < b.x;
>    }
> };
> int main()
> {
>     int n;
>     while(cin>>n&&n)
>     {
>         for(int i=1;i<=n;i++)
>            cin>>a[i].x>>a[i].y;
>         sort(a+1,a+n+1,pt_cmp());
>         int l=a[n].x,c=a[n].y;
>         int ans=1;
>         for(int j=n-1;j>=1;j--)
>         {
>             if(a[j].x==l) continue;
>             else
>                 if(a[j].y>c)
>                 {
>                     c=a[j].y;
>                     l=a[j].x;
>                     ans++;
>                 }
>         }
>         cout<<ans<<endl;        
>     }
>     return 0;
> }

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