CodeForces2A题解

发表于 | 更新于 | 评论数： | 阅读次数：

好吧，非C++选手只好对极其好用的STL望而兴叹了QAQ。

多么显然的map映射啊。

强烈建议STL初学者试着一A。

CodeForces2A Winner

题目描述

The winner of the card game popular in Berland “Berlogging” is determined according to the following rules.
If at the end of the game there is only one player with the maximum number of points, he is the winner.
The situation becomes more difficult if the number of such players is more than one.
During each round a player gains or loses a particular number of points.
In the course of the game the number of points is registered in the line “name score”, where name is a player’s name, and score is the number of points gained in this round, which is an integer number.
If score is negative, this means that the player has lost in the round.
So, if two or more players have the maximum number of points (say, it equals to m ) at the end of the game, than wins the one of them who scored at least m points first.
Initially each player has 0 points. It’s guaranteed that at the end of the game at least one player has a positive number of points.

输入输出格式

输入格式

The first line contains an integer number $n \; 1 \leq n \leq 1000$, $n$ is the number of rounds played. Then follow n lines, containing the information about the rounds in “name score” format in chronological order, where name is a string of lower-case Latin letters with the length from 1 to 32, and score is an integer number between -1000 and 1000, inclusive.

输出格式

Print the name of the winner.

INPUT & OUTPUT ‘s example

Input’s eg #1

1
2
3
4
3
mike 3
andrew 5
mike 2

Output’s eg #1

1
andrew

Input’s eg #2

1
2
3
4
3
andrew 3
andrew 2
mike 5

Outputs’s eg #2

1
andrew

题意翻译

原链接自己看QAQ

分析

经典的STLmap练手题对吧。

map就是STL中的映射模板，映射是个术语，指两个元素的集之间元素相互“对应”的关系，为名词。映射，或者射影，在数学及相关的领域经常等同于函数。 基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。

比如，Rain_Delete上次数学考试考了95，那么Rain_Delete这个名字就在map中对应95这个分数。

定义方法：

1
2
3
#include<map>
using namespace std;
map<类型A,类型B>映射名;

在这个定义中，变量B，就称为相对于变量A的映射。

如何使用？

如果我们要对于string类型的变量Rain_Delete所映射的int类型的变量值+10的话，就可以这么写：

1
2
string s="Rain_Delete";
map[s]+=10;

很简单，对吧？

来讲这道题

我们把输入数据中的人名和分数对应为string类型相对于int类型的map映射。

然后对每一次输入中的分数以其相对应的人名进行操作(+或-)。

但有可能会出现比赛结束后最大分相等的情况。所以我们就要结束之后再$O(n)$访问一遍，查找第一次大于等于最大分的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map> 
#include<cctype>
using namespace std;
namespace FastIO{
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
	inline char getch(){
		if(is==it)
			it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
		return (is==it)?EOF:*is++;
	}
	inline int getint(){
		int res=0,neg=0,ch=getch();
		while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
			ch=getch();
		if(ch=='-'){
			neg=1;ch=getch();
		}
		while(isdigit(ch)){
			res=(res<<3)+(res<<1)+(ch-'0');
			ch=getch();
		}
		return neg?-res:res;
	}
	inline void flush(){
		fwrite(obuf,1,os-obuf,stdout);
		os=obuf;
	}
	inline void putch(char ch){
		*os++=ch;
		if(os==ot)	flush();
	}
	inline void putint(int res){
		static char q[10];
		if(res==0)	putch('0');
		else if(res<0){
			putch('-');
			res=-res;
		} 
		int top=0;
		while(res){
			q[top++]=res%10+'0';
			res/=10;
		}
		while(top--)	putch(q[top]);
	}
} 
using namespace FastIO;
/* consts */
const int MAXN = 1010;
/* definitions */
map<string,int>student,search;
int grade[MAXN],n,x,max_grade=-9999;
string name[MAXN],max_name,s;
/* functions */
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		cin>>name[i]>>grade[i];
		student[name[i]]+=grade[i];
	}
}
inline void find_max(){
	for(int i=1;i<=n;i++)max_grade=max(max_grade,student[name[i]]); 
}
inline void reset(){
	init();
	find_max();
	for(int i=1;i<=n;i++){
		search[name[i]]+=grade[i];
		if(student[name[i]]==max_grade&&search[name[i]]>=max_grade){
			max_name=name[i];
			break;
		}
	} 
}
inline void print_answer(){
	reset();
	cout<<max_name<<endl;
}
int main(int argc,char *argv[]){
	print_answer();
	return 0;
}

THE END