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