POJ 2153 Rank List 地图的应用

POJ 2153 Rank List map的应用

来源：http://poj.org/problem?id=2153

题意：一个人有一些考试，每次得到一个分数，问经过i次考试后总分排名第几。

思路：map的应用，一一对应即可。

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;

const int N = 10010;
int main(){
	//freopen("1.txt","r",stdin);
	int n;
	while(scanf("%d",&n) != EOF){
	   string ss;
	   getchar();
	   map<string,int> mp;
	   map<string,int> :: iterator it;
	   for(int i = 0; i < n; ++i){
		   getline(cin,ss);
		   mp[ss] = 0;
	   }
	   int m;
	   scanf("%d",&m);
	   getchar();
	   for(int i = 0; i < m; ++i){
		   int value = 0,score = 0;
		   for(int j = 0;j < n; ++j){
			   scanf("%d",&score);
			   getchar();
			   getline(cin,ss);
			   mp[ss] += score;
			   if(ss == "Li Ming"){
				   value = mp[ss];
			   }
		   }
		   int cnt = 0,num[N];
		   for(it = mp.begin(); it != mp.end(); ++it){
			   num[cnt++] = it -> second;
		   }
		   sort(num,num+cnt);
		   int lp = 0,rp = cnt - 1,ans = 0;
		   while(lp <= rp){
		      int mid = (lp + rp) / 2;
			  if(num[mid] <= value){
			    ans = mid;
				lp = mid + 1;
			  }
			  else
				  rp = mid - 1;
		   }
		   printf("%d\n",n - ans);
	   }
	}
	return 0;
}