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.0105 sec