2012-07-11 11:04:43Morris
[UVA] 10374 - Election
Problem C: Election
Canada has a multi-party system of government. Each candidate is generally associated with a party, and the party whose candidates win the most ridings generally forms the government. Some candidates run as independents, meaning they are not associated with any party. Your job is to count the votes for a particular riding and to determine the party with which the winning candidate is associated.Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of input contains a positive integer n satisfying 2 <= n <= 20, the number of candidates in the riding. n pairs of lines follow: the first line in each pair is the name of the candidate, up to 80 characters; the second line is the name of the party, up to 80 characters, or the word "independent" if the candidate has no party. No candidate name is repeated and no party name is repeated in the input. No lines contain leading or trailing blanks.
The next line contains a positive integer m <= 10000, and is followed by m lines each indicating the name of a candidate for which a ballot is cast. Any names not in the list of candidates should be ignored.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
Output consists of a single line containing one of:
- The name of the party with whom the winning candidate is associated, if there is a winning candidate and that candidate is associated with a party.
- The word "independent" if there is a winning candidate and that candidate is not associated with a party.
- The word "tie" if there is no winner; that is, if no candidate receives more votes than every other candidate.
Sample Input
1 3 Marilyn Manson Rhinoceros Jane Doe Family Coalition John Smith independent 6 John Smith Marilyn Manson Marilyn Manson Jane Doe John Smith Marilyn Manson
Sample Output
Rhinoceros
果然要用 while(getchar()!='\n'); 代替 getchar();
UVa 好陰
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
while(getchar()!='\n');
map<string, string> r;
map<string, int> s;
string a, b;
while(n--) {
getline(cin, a);
getline(cin, b);
r[a] = b;
}
scanf("%d", &n);
while(getchar()!='\n');
while(n--) {
getline(cin, a);
s[a]++;
}
int top = -1, tie = 0;
string ans = "";
for(map<string, string>::iterator it = r.begin(); it != r.end(); it++) {
int cnt = s[it->first];
if(cnt > top)
top = cnt, tie = 0, ans = it->second;
if(cnt == top)
tie++;
}
if(tie != 1)
ans = "tie";
cout << ans << endl;
if(t)
puts("");
}
return 0;
}