记录编号	33360	评测结果	AAAAAAAAAA
题目名称	韩国明星	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	2.926 s
提交时间	2011-11-10 13:46:48	内存使用	2.17 MiB

#include<fstream>
#include<cstdlib>
#include<string>
using namespace std;
ifstream fin("star.in");
ofstream fout("star.out");
int n,K;
class STAR
{
public:
	string name;
	long long like,where;
}Star[100002];
string S,SS;

int Compare(const void *p1,const void *q1)
{
int i,Lp,Lq;
STAR *p=(STAR *)p1;
STAR *q=(STAR *)q1;
Lp=p->name.length();
Lq=q->name.length();
	for(i=0;i<=(Lp>Lq?Lq:Lp)-1;i++)
	{
		if(p->name[i] > q->name[i])
			return 1;
		if(p->name[i] < q->name[i])
			return -1;
	}
	if(Lp>Lq)
		return 1;
	if(Lq>Lp)
		return -1;
	return 0;
}

int find(int st,int en,string *p)
{
int i,mid,l1,l2;bool flag,bo;
	for(;st!=en;)
	{
		mid=st+en;mid/=2;
		S="\0";
		S=Star[mid].name;
	l1=S.length();l2=(*p).length();
		flag=true;//??????????????????????
		bo=true;//?????????????????????
		for(i=0;i<=(l1>l2?l2:l1)-1;i++)
		{
			if(S[i] > (*p)[i])
			{
				flag=false;
				bo=false;
				break;
			}
			if(S[i] < (*p)[i])
			{
				flag=true;
				bo=false;
				break;
			}
		}
		if(bo==true)
		{
			if(l1>=l2)
				flag=false;
			else
				flag=true;
		}
		
		if(flag==true)
			st=mid+1;
		else
			en=mid;
	}
	return st;
}
void init()
{
int i,pos,value;
string S="\0";
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>Star[i].name;
		Star[i].where=i;
	}
	qsort(Star+1,n,sizeof(STAR),Compare);	
	fin>>K;
	for(i=1;i<=K;i++)
	{
		SS="\0";
		fin>>SS;
		fin>>value;
		pos=find(1,n,&SS);
		Star[pos].like+=value;
	}
}
int Com(const void *p,const void *q)
{
	return ((STAR *)q)->like - ((STAR *)p)->like;
}

void OUTPUT()
{
int i;
	for(i=1;i<=n;i++)
		fout<<Star[i].name<<endl<<Star[i].like<<endl;
}

int main()
{
	init();	
	
	qsort(Star+1,n,sizeof(STAR),Com);
	
	OUTPUT();
	
	fin.close();
	fout.close();
	return 0;
}