首页 > 代码库 > TOJ-1322 Election

TOJ-1322 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 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

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

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



Source: Waterloo Local Contest Jun. 19, 1999

题目理解起来毫无难度,但是做的时候发生了很奇怪的事情。开始时,在输入n或m后,gets()前,我用cin.get或getchar吃多余字符,WA。。。

去掉cin.get或getchar(),TLE。。。为此我在网上把别人的代码抄了又抄,只有一个能AC,就是scanf("%d\n",&n)。为什么,我不知道,希望有大牛

能给我解释一下。改来改去我的代码和别人的也长的差不多了,本来我只用了一个map来着,不过两个map确实写起来容易多了。

 

#include <stdio.h>
#include <iostream>
#include <map>
#include <string.h>
#include <memory.h>
using namespace std;
struct str{
    char n[82];
    friend bool operator < (str a, str b)  
    {  
        return strcmp(a.n, b.n)<0;  
    }
};


int main(){
    int i,n,m;
    str cant,pty;
    map<str,str> cdt;
    map<str,int> num;
    scanf("%d\n",&n);

    for(i=0;i<n;i++){
        gets(cant.n);
        gets(pty.n);
        cdt[cant] = pty;
        num[cant] = 0; 
    }
    map<str,int>::iterator iter,temp;
    map<str,str>::iterator temp1;
    scanf("%d\n",&m);
    for(i=0;i<m;i++) 
    {  
        gets(cant.n);     
        iter=num.find(cant);
        iter->second++;
    }  
    int k = 0;
    temp=num.begin();
    for(iter=num.begin();iter!=num.end();iter++){
        if(iter->second == temp->second) k++;  
        else  
        {  
            if(iter->second > temp->second)   
            {  
                temp = iter;  
                k=1;  
            }  
        }
    }
    if(k>1)    printf("tie\n");
    else{
        temp1 = cdt.find(temp->first);
        printf("%s\n",temp1->second.n);
    }    
    return 0;
}

 

TOJ-1322 Election