Posted on 2009-10-29 21:39
Uriel 阅读(263)
评论(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;
}
