Rank List
|
Time Limit: 10000MS |
|
Memory Limit: 65536K |
|
Total Submissions: 6561 |
|
Accepted: 2091 |
Description
Li Ming is a good student. He always asks the teacher about his rank in his class after every exam, which makes the teacher very tired. So the teacher gives him the scores of all the student in his class and asked him to get his rank by himself. However, he has so many classmates, and he can’t know his rank easily. So he tends to you for help, can you help him?
Input
The first line of the input contains an integer N (1 <= N <= 10000), which represents the number of student in Li Ming’s class. Then come N lines. Each line contains a name, which has no more than 30 letters. These names represent all the students in Li Ming’s class and you can assume that the names are different from each other.
In (N+2)-th line, you'll get an integer M (1 <= M <= 50), which represents the number of exams. The following M parts each represent an exam. Each exam has N lines. In each line, there is a positive integer S, which is no more then 100, and a name P, which must occur in the name list described above. It means that in this exam student P gains S scores. It’s confirmed that all the names in the name list will appear in an exam.
Output
The output contains M lines. In the i-th line, you should give the rank of Li Ming after the i-th exam. The rank is decided by the total scores. If Li Ming has the same score with others, he will always in front of others in the rank list.
Sample Input
3
Li Ming
A
B
2
49 Li Ming
49 A
48 B
80 A
85 B
83 Li Ming
Sample Output
1
2
Source
POJ Monthly,Li Haoyuan
給定每個人的成績，查詢某一人的名次。
用MAP建立人名和成績的對應關系，用cnt數組（最多5000個元素）記錄成績為某個分數的人數，不過由于總人數較少(最多只有10000人),直接遍歷也不比建立計數排序數組多用多少時間,計數排序的優勢并不顯著.
用hash函數或者二分查找也應該能解決這個問題.
/**//*Source?Code
Problem:?2153??User:?y09
Memory:?1236K??Time:?1204MS?
Language:?C++??Result:?Accepted?
Source?Code?*/
#include?<iostream>
#include<string>
#include<map>
using?namespace?std;
int?main(int?argc,?char?*argv[])
{
????int?n,m;
????int?i,j;
????char?str[200];
????string?str1;
????
????map<string?,int>score;
????
????scanf("%d",&n);
????getchar();
????for?(i=0;i<n;i++?)
????{
????????gets(str);
????????str1=str;
????????score[str1]=0;
????}
????
????int?cnt[5005]={0};
????
????scanf("%d",&m);
????string?li="Li?Ming";
????int?rank=0;
????int?s=0;
????int?temp=0;
????int?temp2=0;
????int?num;
????for(int?k=0;k<m;k++)
????{
????????for(i=0;i<n;i++)
????????{
????????????scanf("%d",&num);
????????????getchar();
????????????gets(str);
????????????str1=str;
????????????temp2=score[str1];
????????????score[str1]=num+temp2;
????????????cnt[num+temp2]++;
????????}
????????s=score[li];
????????rank=1;
????????temp+=100;
????????for(i=temp;i>s;i--)
????????{
????????????rank+=cnt[i];
????????????cnt[i]=0;
????????}
????????for(i=s;i>=0;i--)
????????????cnt[i]=0;
????????printf("%d\n",rank);
????}
????return?0;
}