codechef 20131月月赛大水题

记忆太多

　　http://www.codechef.com/JAN13/problems/CVOTE
　　

Chef of the Year
　　Problem code: CVOTE

• Submit
  
• My Submissions
  
• All Submissions
  

　　Chefs from all over the globe gather each year for an international convention. Each chef represents some country. Please, note that more than one chef can represent a country.
　　Each of them presents their best dish to the audience. The audience then sends emails to a secret and secure mail server, with the subject being the name of the chef whom they wish to elect as the
"Chef of the Year".
　　You will be given the list of the subjects of all the emails. Find the country whose chefs got the most number of votes, and also the chef who got elected as the
"Chef of the Year" (the chef who got the most number of votes).
　　Note 1
　　If several countries got the maximal number of votes, consider the country with the lexicographically smaller name among them to be a winner. Similarly if several chefs got the maximal number of votes, consider the chef with the lexicographically smaller
name among them to be a winner.
　　Note 2
　　The string A = a1a2...an is called lexicographically smaller then the string
B = b1b2...bm in the following two cases:

• there exists index i ≤ min{n, m} such that
  aj = bj for 1 ≤ j < i and
  ai < bi;
  
• A is a proper prefix of B, that is,
  n < m and aj = bj for
  1 ≤ j ≤ n.
  

　　The characters in strings are compared by their ASCII codes.
　　Refer to function strcmp in C or to standard comparator
< for string data structure in C&#43;&#43; for details.

Input
　　The first line of the input contains two space-separated integers N and
M denoting the number of chefs and the number of emails respectively. Each of the following
N lines contains two space-separated strings, denoting the name of the chef and his country respectively. Each of the following
M lines contains one string denoting the subject of the email.

Output
　　Output should consist of two lines. The first line should contain the name of the country whose chefs got the most number of votes. The second line should contain the name of the chef who is elected as the
&quot;Chef of the Year&quot;.

Constraints

• 1 ≤ N ≤ 10000 (104)
  
• 1 ≤ M ≤ 100000 (105)
  
• Each string in the input contains only letters of English alphabets (uppercase or lowercase)
  
• Each string in the input has length not exceeding 10
  
• All chef names will be distinct
  
• Subject of each email will coincide with the name of one of the chefs
  

Example 1

Input:
1 3
Leibniz Germany
Leibniz
Leibniz
Leibniz
Output:
Germany
Leibniz

Example 2

Input:
4 5
Ramanujan India
Torricelli Italy
Gauss Germany
Lagrange Italy
Ramanujan
Torricelli
Torricelli
Ramanujan
Lagrange
Output:
Italy
Ramanujan

Example 3

Input:
2 2
Newton England
Euclid Greece
Newton
Euclid
Output:
England
Euclid

Explanation
　　Example 1. Here we have only one chef Leibniz and he is from
Germany. Clearly, all votes are for him. So Germany is the country-winner and
Leibniz is the &quot;Chef of the Year&quot;.
　　Example 2. Here we have chefs Torricelli and
Lagrange from Italy, chef Ramanujan from
India and chef Gauss from Germany.
Torricelli got 2 votes, while Lagrange got one vote. Hence the
Italy got 3 votes in all. Ramanujan got also 2 votes. And so
India got 2 votes in all. Finally Gauss got no votes leaving
Germany without votes. So the country-winner is Italy without any ties. But we have two chefs with 2 votes:
Torricelli and Ramanujan. But since the string
&quot;Ramanujan&quot; is lexicographically smaller than &quot;Torricelli&quot;, then
Ramanujan is the &quot;Chef of the Year&quot;.
　　Example 3. Here we have two countries with 1 vote: England and
Greece. Since the string &quot;England&quot; is lexicographically smaller than
&quot;Greece&quot;, then England is the country-winner. Next, we have two chefs with 1 vote:
Newton and Euclid. Since the string &quot;Euclid&quot; is lexicographically smaller than
&quot;Newton&quot;, then Euclid is the &quot;Chef of the Year&quot;.
　　
　　


　　


　　题意：  输入nm  n个字符串对     表示某个人对应某个国家
　　然后输入 m个人  表示每个人得到的金牌数加1   对应的国家也要加1


　　输出得到金牌数最多的国家 和 最多的人    相同的按字典序
　　


　　思路：
　　3个map水体
　　#include<string>
#include<stdio.h>
#include<map>
#include<string.h>
#include<iostream>
using namespace std;
map<string,string>mp1;
map<string,int>mp2;
map<string,int>mp3;
map<string,int>::iterator it,it1,it2;
int main()
{
int n,m,i,j,k;
char s1[100],s2[100];
char ans1[100],ans2[100];
while(scanf(&quot;%d %d&quot;,&n,&m)!=EOF)
{
mp1.clear();
mp2.clear();
mp3.clear();
while(n--)
{
scanf(&quot;%s %s&quot;,s1,s2);
mp1[s1]=s2;
}
while(m--)
{
scanf(&quot;%s&quot;,s1);
mp2[s1]++;
mp3[mp1[s1]]++;
// mp3[s1]++;
}
//strcpy(char_str,string_str.c_str());
int mmax=0;
for(it=mp2.begin();it!=mp2.end();it++)
{
if(it->second>mmax) {mmax=it->second;strcpy(ans1,it->first.c_str());}
}
mmax=0;
for(it=mp3.begin();it!=mp3.end();it++)
{
if(it->second>mmax) {mmax=it->second;strcpy(ans2,it->first.c_str());}
}
printf(&quot;%s\n%s\n&quot;,ans2,ans1);
//cout<<ans1<<ans2<<endl;
}
return 0;
}