Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 2153 Rank List---sort+二分

Posted on 2009-10-29 21:39 Uriel 阅读(261) 评论(0)  编辑 收藏 引用 所属分类: POJ
曾经看到Discuss有说二叉排序树什么的,就丢下来了。。
然后很久之后竟然水过了。。sort+二分查找。。不过效率有点低。。G++3329Ms。。C++3922Ms。。
/*Problem: 2153  User: Uriel 
   Memory: 1224K  Time: 3922MS 
   Language: C++  Result: Accepted
*/
 


#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
#include
<algorithm>
using namespace std;

#define MAXN 10010

struct M
{
    
char name[100];
    
int sco;
    
int flag;
}
;

M P[MAXN];
int n,m;

bool cmp(M a,M b)
{
    
return strcmp(a.name,b.name)<0;
}


bool cmp2(M a,M b)
{
    
if(a.sco != b.sco)return a.sco > b.sco;
    
return a.flag < b.flag;
}


int BSearch(char *a)
{
    
int l=1,r=n;
    
while(l<=r)
    
{
        
int mid=(l+r)/2;
        
if(strcmp(a,P[mid].name)<0)
        
{
            r
=mid-1;
        }

        
else if(strcmp(a,P[mid].name)==0)return mid;
        
else
        
{
            l
=mid+1;
        }

    }

    
return l;
}


int main()
{
    
int i,s,x;
    
char str[100];
    scanf(
"%d",&n);
    getchar();
    
for(i=1;i<=n;i++)
    
{
        gets(P[i].name);
        
if(strcmp(P[i].name,"Li Ming")==0)
        
{
            P[i].flag
=0;
        }

        
else
        
{
            P[i].flag
=1;
        }

        P[i].sco
=0;
    }

    scanf(
"%d",&m);
    
while(m--)
    
{
        sort(P
+1,P+n+1,cmp);
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d ",&s);
            gets(str);
            x
=BSearch(str);
            P[x].sco
+=s;
        }

        sort(P
+1,P+n+1,cmp2);
        
for(i=1;i<=n;i++)
        
{
            
if(strcmp(P[i].name,"Li Ming")==0)printf("%d\n",i);
        }

    }

    
return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理