1309.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1309 on 2005-12-27 at 16:39:55 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <list>
#include <map>
using namespace std;

const int MAX = 128;
const int L_MAX = 16;
const int INF = 20000000;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

int main()
{
	list<int> ballot[MAX];
	map<const char*, int, cmp> cand;
	char name[MAX][L_MAX], tie[MAX][L_MAX], ch;
	int n, m, p, i;
	bool elim[MAX];
	
	while(scanf("%d %d", &n, &m) != EOF && n*m != 0) {
		int cn = 0; cand.clear(); getchar();
		for(i = 0; i < m; i++) {
			ballot[i].clear();
			while(true) {
				while((ch = getchar()) == ' ') ;
				if(ch == '\n') break;
				else {
					ungetc(ch, stdin);
					scanf("%s", name[cn]);
					if(cand.count(name[cn]) == 0) p = cn++, cand[name[p]] = p;
					else p = cand.find(name[cn])->second;
					ballot[i].push_back(p);
				}
			}
		}
		memset(elim, false, sizeof(elim));
		bool win = false;
		int remain = m, candn = n, vote[MAX], stack[MAX], winner;
		while(!win) {
			memset(vote, false, sizeof(vote));
			for(i = 0; i < m; i++) {
				bool erase = true;
				while(!ballot[i].empty() && elim[*(ballot[i].begin())]) {
					ballot[i].erase(ballot[i].begin());
					erase = false;
				}
				if(!ballot[i].empty()) vote[*(ballot[i].begin())]++;
				else if(!erase) remain--;
			}
			int top = 0, min = INF;
			for(i = 0; i < n; i++) {
				if(!elim[i]) {
					if(2*vote[i] > remain) win = true, winner = i;
					else if(vote[i] < min) stack[0] = i, min = vote[i], top = 1;
					else if(vote[i] == min) stack[top++] = i;
				}
			}
			if(top == candn) break;
			else {
				for(i = 0; i < top; i++) elim[stack[i]] = true;
				candn -= top;
			}
		}
		if(win) printf("%s won", name[winner]);
		else {
			int tn = 0;
			for(i = 0; i < n; i++) {
				if(!elim[i]) strcpy(tie[tn++], name[i]);
			}
			qsort(tie, tn, sizeof(tie[0]), (int(*)(const void*, const void*))strcmp);
			printf("it is a tie between");
			for(i = 0; i < tn; i++) {
				if(i != 0) printf(" and");
				printf(" %s", tie[i]);
			}
		}
		putchar('\n');
	}
	
	return 0;
}