北大 acm 2153 Rank List 解题报告

Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 5897 Accepted: 1843

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

3Li MingAB249 Li Ming49 A48 B80 A85 B83 Li Ming

Sample Output

12

题意：找出Li Ming的排名，注意，是总分排名，即每次都要叠加分数 据一些牛人的方法介绍此题可用map做，比较方便，但本人才疏学浅stl没学， 最近刚知道一个函数就是qsort，所以用这个函数做，不可否认这个函数确实很强大

代码

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

struct people
{
char name[35];
int socre;
};

int compare(const void *a,const void *b)       //对字符进行排序
{
  return strcmp((*(people *)a).name,(*( people *)b).name);     //(*(In *)a)->str , (*(In *)b)->str ;
}

int compare1(const void *a ,const void *b)       //对分数进行排序
{
  return (*( people *)b).socre-(*(people *)a).socre;
}

int main()
{
  people student[10005];
  people stdu[10005];
  int n,m;
  int i;

  while(scanf("%d ",&n)!=-1)      //scanf记得还要读入一个空格，或者改为scanf("%d",&n);后面加一个getchar()；读入一个scanf的回车符
  {

    for (i=0;i<n;i++)
    {
      gets(student[i].name);
      student[i].socre=0;
    }

    cin>>m;

    while(m--)
    {
      for (i=0;i<n;i++)
      {
        scanf("%d ",&stdu[i].socre);
        gets(stdu[i].name);
      }

      qsort(student,n,sizeof(student[0]),compare);   //这个连个排序主要是让student，和stdu两个名字顺序一样，然后依次相加
      qsort(stdu,n,sizeof(student[0]),compare);


      for(i=0;i<n;i++)
        student[i].socre+=stdu[i].socre;

      qsort(student,n,sizeof(student[0]),compare1);    //按照分数进行排序

      for(i=0;i<n;i++)
        if(strcmp(student[i].name,"Li Ming")==0)
        {
          while(student[i-1].socre==student[i].socre)
            i--;//排除出现相等的分数情况，Li Ming要在前面
          cout<<i+1<<endl;
          break;
        }
    }
  }

  return 0;
}