• 如果喜欢本站,您可以按CTRL+D收藏本站,方便下次访问。

  • 欢迎来自五湖四海的朋友,期待为您分享有价值的资源 :oops:

POJ 2153-Rank List –map / 计数排序

POJ解题 第四度 10年前 (2010-08-28) 42次浏览 0个评论 扫描二维码

file

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

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;
}

本网站采用BY-NC-SA 4.0协议进行授权 | 转载请注明原文链接:https://www.disidu.com/post/1018.html
如果觉得本文对您有帮助或者您心情好~可以微信打赏支持一下本站:↓↓↓
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址