PKU 2153 Rank List
http://poj.org/problem?id=2153
Li Mingという人がいるクラスの人数分のテストの点数データが渡されるので、それをもとに、点数の累積値でみたLi Mingの順位をテスト毎に答えろというような問題。
最初それぞれのテスト単体で考えるのかと思いました。
普通にやるとTLEしたので、ハッシュ使いました。
typedef struct _node{ char key[40]; int val; _node* next; }node; const int hashMod=30000000; node* hash[hashMod]; int number; node ent[10000]; int getnum(char in[]){ int ha=0; for(char*p=in;*p;++p)ha=(ha*67+*p)%hashMod; for(node*p=hash[ha];p;p=p->next){ if(strcmp(in,p->key)==0){ return p->val; } } node*p=hash[ha]; hash[ha]=ent+number; hash[ha]->next=p; strcpy(hash[ha]->key,in); hash[ha]->val=number++; return number-1; } void add(char in[],int val){ int ha=0; for(char*p=in;*p;++p)ha=(ha*67+*p)%hashMod; for(node*p=hash[ha];p;p=p->next){ if(strcmp(in,p->key)==0){ p->val+=val; return; } } node*p=hash[ha]; hash[ha]=ent+number++; hash[ha]->next=p; strcpy(hash[ha]->key,in); hash[ha]->val=val; } char in[40]; main(){ int n; scanf("%d",&n); cin.get(); rep(i,n){ char in[100]; gets(in); } int m; cin>>m; while(m--){ int po; rep(i,n){ int val; scanf("%d ",&val); gets(in); add(in,val); if(strcmp(in,"Li Ming")==0)po=getnum(in); } int ans=1; rep(i,n)ans+=ent[i].val>po; cout<<ans<<endl; } }