U E D R , A S I H C RSS

Australian Voting/곽세환

��감

2005/03/13 Accepted(P.E.) 0:01.191 520
���� ��근�� ���� ������ 고����.
���������� 감���� ���� ��그� ����
������ ���� ��.
�����기�� �각�� ��간�� ����
���� ������ ��� ���������� ������������ ������ 그�� ��. 그���� �� ����� �� ����.
������ ������ 기�� ���� ������ ���������� ���� ������.

����

~cpp 
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <string.h>

int main()
{
	int numberOfCase;
	cin >> numberOfCase;
	int i, tc;
	for (tc = 0; tc < numberOfCase; tc++)
	{
		int numberOfCandidates;
		char candidates[20][81];
		int votes[1000][20] = {{0}};
		int rank[1000] = {{0}};
		int votesPerCandidates[20] = {{0}};
		
		cin >> numberOfCandidates;
		cin.get();
		for (i = 0; i < numberOfCandidates; i++)
			cin.getline(candidates[i], 81);

		int numberOfVoters = 0;
		char temp[60];

		
		while (cin.getline(temp, 60) && strcmp(temp, ""))
		{
			votes[numberOfVoters][0] = atoi(strtok(temp, " "));
			for (i = 1; i < numberOfCandidates; i++)
				votes[numberOfVoters][i] = atoi(strtok(NULL, " "));
			numberOfVoters++;
		}

		bool foundWinner = false;
		bool foundTie = true;
		int winner;
		int sameVote;
		
		int eliminated[20];
		int eliminatedCnt = 0;
		while (true)
		{
			for (i = 0; i < numberOfCandidates; i++)
			{
				votesPerCandidates[i] = 0;
			}

			// ���� 개���� �������� 구��
			for (i = 0; i < numberOfVoters; i++)
			{
				votesPerCandidates[votes[i][rank[i]] - 1]++;
			}

			// ������ ����(���� 개���� ������)
			/*for (i = 0; i < numberOfCandidates; i++)			
				cout << votesPerCandidates[i] << " ";
			cout << endl;*/
			
			// ������ ����(��� ��구 ������)
			/*for (i = 0; i < numberOfVoters; i++)
			{
				cout << votes[i][rank[i]] << " ";
			}
			cin.get();*/

			//  50% �과거�� ������� �� ��� ����
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (votesPerCandidates[i] > 0.5 * numberOfVoters)
				{
					foundWinner = true;
					winner = i;
					break;
				}
			}
			foundTie = true;
			sameVote = 0;
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (votesPerCandidates[i] == 0)
					continue;
				if (sameVote == 0)
					sameVote = votesPerCandidates[i];
				else if (sameVote != votesPerCandidates[i])
					foundTie = false;
			}
			if (foundWinner || foundTie)
				break;

			// ��� �� �������� �� ������ �� ��권���� ���� ���� 그 ���������� ���(2��계)
			int minVote = 1001;
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (votesPerCandidates[i] == 0)
					continue;
				if (minVote > votesPerCandidates[i])
					minVote = votesPerCandidates[i];
			}

			// 1-��거�� ���� �� ����고
			for (i = 0; i < numberOfVoters; i++)
			{
				int j;
				if (votesPerCandidates[votes[i][rank[i]] - 1] == minVote)
				{
					for (j = 0; j < eliminatedCnt; j++)
					{
						if (eliminated[j] == votes[i][rank[i]])
							break;
					}
					if (j == eliminatedCnt)
						eliminated[eliminatedCnt++] = votes[i][rank[i]];
				}
			}

			// 2-��거�� ���� ���� ���� ���������� ���
			for (i = 0; i < numberOfVoters; i++)
			{
				int j;
				if (votesPerCandidates[votes[i][rank[i]] - 1] == minVote)
				{
					bool foundNextCandidates;
					while (true)
					{
						rank[i]++;
						
						foundNextCandidates = true;
						for (j = 0; j < eliminatedCnt; j++)
							if (votes[i][rank[i]] == eliminated[j])
							{
								foundNextCandidates = false;
								break;
							}
						if (foundNextCandidates)
							break;
					}
				}
			}
			// ������ ����(��거�� ��)
			/*for (i = 0; i < eliminatedCnt; i++)
				cout << eliminated[i] << " ";
			cout << endl;*/
		}
		if (foundWinner)
			cout << candidates[winner] << endl;
		else if (foundTie)
		{
			for (i = 0; i < numberOfCandidates; i++)
			{
				if (sameVote == votesPerCandidates[i])
					cout << candidates[i] << endl;
			}
		}
		cout << endl;
	}

	return 0;
}

���

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:33
Processing time 0.0742 sec