算法

POJ2153总结

Rank List

题目来源

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

我的代码

用Map记录每个学生的总分,然后每一次考试过后将总分写入一个vector进行降序排序,用lower_bound查找。

#include <iostream>//数据输入输出流
#include <cstring>//字符串操作函数
#include <cstdlib>//定义杂项函数及内存分配函数
#include <cmath>//C中的数学函数
#include <string>//c++中的string类 他不能用strcpy等c函数去操作
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int n,m;
	string temp;
	map<string,int> sum;
	scanf("%d",&n);
	getchar();
	for (int i=0;i<n;i++)
	{
		getline(cin,temp);
		sum[temp]=0;
	}
	scanf("%d",&m);
	getchar();
	for (int o=1;o<=m;o++)
	{
		int grade;
		vector<int> grades;
		for (int i=0;i<n;i++)
		{
			scanf("%d",&grade);
			getchar();
			getline(cin,temp);//cout<<temp<<grade[i]<<endl;
			sum[temp]+=grade;
			grades.push_back(sum[temp]);
		}
		sort(grades.begin(),grades.end(),cmp);
		int rank=lower_bound(grades.begin(),grades.end(),sum["Li Ming"],greater<int>())-grades.begin();
		printf("%d\n",rank+1);
	}
	return 0;
}

还好这题时间限制10s,不然必超时。

map

反思

为什么poj不能用unorder_map啊?感觉效率会高很多,虽然我的dev一开始用unorder_map头文件报错,我按照网上的方法挑了一下之后可以了,但是poj还是编译错误。

方案一(个人没用)

方案二(个人有用)

发表评论