学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2648

题目大意：有N个店，他们的商品价格每天都在上涨，问你 ith天有个叫memory的店，它的价格在所有商店中，有几个高过它，输出它的排名，有k个高过它，它就是第k+1名。

解题思路：哈希搜索

#include <iostream><br /> #include <vector><br /> using namespace std;</p> <p>struct node<br /> {<br /> char str[35];<br /> int price;<br /> node(){price = 0;}<br /> };</p> <p>const int prime = 100007;<br /> int aa[prime];<br /> vector<node>LIST[prime];</p> <p>unsigned int BKDRHash(char *str)<br /> {<br /> unsigned int seed = 31,key = 0;<br /> while(*str)<br /> key = key*seed+ *str++;<br /> return key&(0x7fffffff);<br /> }</p> <p>int main()<br /> {<br /> int n,key,val,len1,m,i,count,res,j,len,price;<br /> node a;<br /> char s[35];</p> <p> while (scanf("%d",&m)!=EOF)<br /> {<br /> /*多组数据，要清空vector容器*/<br /> for (i=0;i<prime;i++)<br /> LIST[i].clear();</p> <p> for(i=0;i<m;i++)<br /> {<br /> scanf("%s",s);<br /> strcpy(a.str,s);<br /> key = BKDRHash(s)%prime;<br /> LIST[key].push_back(a);<br /> }<br /> scanf("%d",&n);<br /> while (n--)<br /> {<br /> count = 0;/*统计有几个shop价格大于memory*/<br /> len = 0;/*记录所有价格*/<br /> price = 0;<br /> for(i=0;i<m;i++)<br /> {<br /> scanf("%d%s",&val,s);<br /> key = BKDRHash(s)%prime;<br /> len1 = LIST[key].size();<br /> for (j=0;j<len1;j++)<br /> {<br /> if(!strcmp(LIST[key][j].str,s))<br /> {<br /> LIST[key][j].price+=val;<br /> res = LIST[key][j].price;/*记录数值*/<br /> break;<br /> }<br /> }<br /> if(strcmp(s,"memory")!=0)<br /> aa[len++] = res;/*入数组*/<br /> else<br /> price = res;/*记录memory店的价格*/<br /> }<br /> for (i=0;i<len;i++)<br /> {<br /> if(price<aa[i])<br /> count++;<br /> }<br /> printf("%d/n",count+1);<br /> }<br /> }<br /> return 0;<br /> }