Problem Description
Every girl likes shopping,so does dandelion.Now she
finds the shop is increasing the price every day because the Spring Festival is
coming .She is fond of a shop which is called "memory". Now she wants to know
the rank of this shop's price after the change of everyday.
Input
One line contians a number n ( n<=10000),stands for the number of shops.
Then n lines ,each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.)stands for the name of the shop.
Then a line contians a number m (1<=m<=50),stands for the days .
Then m parts , every parts contians n lines , each line contians a number s and a string p ,stands for this day ,the shop p 's price has increased s.
Output
Contains m lines ,In the ith line print a number of the
shop "memory" 's rank after the ith day. We define the rank as :If there are t
shops' price is higher than the "memory" , than its rank is t+1.
Sample Input
3
memory
kfc
wind
2
49 memory
49 kfc
48 wind
80 kfc
85 wind
83 memory
Sample Output
1
2
這題目的意思就是有n個(gè)商店。這n個(gè)商店會(huì)進(jìn)行m天的銷售，你需要每一天輸出一次' memory' 的排名球散，而且這個(gè)商品的價(jià)錢是會(huì)累加的
例如第一天 kfc是49 第二天kfc在49的基礎(chǔ)上在漲80 也就是 129
這道題我也是參考了很多人的代碼够颠，在不斷的摸索下還是TLE 我就在想我到底錯(cuò)在那里
難道是因?yàn)槲覜]有用vector的原因嗎？在我不斷檢測(cè)我的代碼發(fā)現(xiàn)我錯(cuò)在了一個(gè)死循環(huán)上威蕉，我忘記寫p=p->next后來加上ac了
頭疼 颗品。、续滋。。 一定一定要好好的檢查自己的代碼孵奶。
好了我們來說下這道題要怎么想
簡(jiǎn)單來說這道題運(yùn)用了Hash + map 或者 Hash +?vector 或者向我一樣 Hash + 結(jié)構(gòu)體指針數(shù)組
來說下為什么這道題用Hash疲酌，因?yàn)檫@道題你想要他快速的算出來你就必須讓每天對(duì)應(yīng)的商品加上對(duì)應(yīng)的價(jià)錢對(duì)把
例如 ? 第一天?
49 memory
49 kfc
48 wind
那么我們就要找memory在那里啊，是不是第一想到的就是用for循環(huán)去找但是每次都那么找可以嗎
數(shù)據(jù)量是10000了袁，也就是說光是累加商品價(jià)格你就要花費(fèi)大量的時(shí)間去尋找朗恳，我們有沒有辦法一下子找到這個(gè)memory呢？
所以我們就用了Hash表载绿，這樣給我們省下大量的時(shí)間
使用了Hash表我們就需要給我們的Hash表定一個(gè)key函數(shù)粥诫，以及一個(gè)沖突處理機(jī)制
這里key函數(shù)的意義就是將字符串memory變成一個(gè)整形的數(shù)，我們就可以Hash[ key ] 直接拿到值了對(duì)不對(duì)
所以我們需要做這個(gè)key函數(shù)
key 函數(shù)：
這里用的是BKDR Hash
int nums=0崭庸，seed=31怀浆；
for(inti=0;str[i]!='\0';i++)
??????? nums=nums*seed+str[i];
nums=nums % 10005; ?這里為什么要%10005呢 ？ 是因?yàn)槲覀兊腍ash數(shù)組就[10005]就那么大為了防止這個(gè)數(shù)超出去
那這里的seed為什么是31呢怕享，這里的seed甚至可以是131执赡，是其他的素?cái)?shù)只是為了盡可能的每個(gè)nums都不一樣而然防止沖突
那這里key求出來，一旦數(shù)據(jù)量大沖突是不可避免的對(duì)把函筋∩澈希總是有一個(gè)字符串算出來的key是和之前的key相等對(duì)不對(duì)
這時(shí)候我們的沖突處理就出來拉
我們將這個(gè)hash表以鏈?zhǔn)酱嫫饋?/p>
這里如果地址沖突了我們就在原本的鏈尾加入新的結(jié)點(diǎn)就好拉
下面是ac代碼
實(shí)在不懂怎么貼代碼上來。跌帐。發(fā)圖片 了首懈。绊率。。
這里的ins就是我們的key函數(shù)+插入鏈尾的操作
這里的find函數(shù)是為了查找str 然后找到后把每天變化的價(jià)錢加入我們的值里
第一次寫這種類型的文究履，真的不會(huì)貼代碼滤否。。頭巨疼挎袜。顽聂。。
