ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, B 解答

B: 当選者を探せ!

問題

選挙の開票を行う。26人の候補者があり、票の総数はnで、1票づつ開けていく。
単独首位で当選確実になった候補者が初めて決まるのは何票目で誰か、出力せよ。
ただし開票して首位が2人以上いるならば"TIE"と出力せよ。

解法

「得票数が2位の候補者に残りの全ての票が入ったとしても得票数1位の人を上回ることができなくなった」時点で首位確定。
1票づつ1位と2位を見つければよい。
26人しかいないので毎回ソートする。

コード

#include<cstdio>
#include<algorithm>
using namespace std;

int N;
pair<int, char> P[26];
char buf[9];

int main() {

    while (scanf("%d", &N), N) {

	for (int i=0; i<26; i++) P[i] = make_pair(0, 'A' + i);

	char ansS[9] = "TIE";
	int ansI = -1;

	for (int i=0; i<N; i++) {
	    scanf("%s", buf);

	    for (int j=0; j<26; j++) 
		if (P[j].second == buf[0])
		    P[j].first++;

	    sort(P, P+26);

	    if (ansI == -1 && P[25].first > P[24].first + N - i - 1) {
		ansS[0] = P[25].second; ansS[1] = '\0';
		ansI = i + 1;
	    }
	}

	if (ansI == -1) {
	    puts("TIE");
	} else {
	    printf("%s %d\n", ansS, ansI);
	}
    }

    return 0;
}