U E D R , A S I H C RSS

Australian Voting/문보창

소감

2005/02/19 Accepted(P.E.) 0:01.689 572
Presentation Error를 잡아야 한다. 수행시간과 메모리사용량 또한 만족할 만한 수준이 아니다.

코드

~cpp 
// no10142 - Australian Voting
#include <iostream>
#include <string>
using namespace std;

bool elect(const char can[][81], const int & nCan, const int bal[][20], const int & nBal, string & win);

int main()
{
	int nCase;
	cin >> nCase;
	cin.get();
	cin.get();	
	int nCandidate;
	char candidate[20][81];	
	int ballot[1000][20];
	string winner;
	int i, j;
	for (i=0; i<nCase; i++)
	{
		cin >> nCandidate;
		cin.get();
		for (j=0; j<nCandidate; j++)
			cin.getline(candidate[j], 81, '\n');
		int nBallot = 0;
		while(true)
		{
			for (j=0; j<nCandidate; j++)
				cin >> ballot[nBallot][j];
			nBallot++;
			cin.get();
			if (cin.peek() == '\n' || cin.peek() == EOF)
				break;
		}
		elect(candidate, nCandidate, ballot, nBallot, winner);	
	}
	winner[winner.size()-1] = '\0';
	cout << winner;	
	return 0;
}

bool elect(const char can[][81], const int & nCan, const int bal[][20], const int & nBal, string & win)
{
	int poll[20];
	bool died[20] = {0,};
	int max, min, maxIndex;
	int i, j;	
	while (true)
	{
		for (i=0; i<nCan; i++)
			poll[i] = 0;
		for (i=0; i<nBal; i++)
		{
			for (j=0; j<nCan; j++)
			{
				if (!died[bal[i][j]-1])
				{
					poll[bal[i][j]-1]++;
					break;
				}
			}
		}
		max = 0;
		min = 1001;
		for (i=0; i<nCan; i++)
		{
			if (!died[i])
			{
				if (max < poll[i])
				{
					max = poll[i];
					maxIndex = i;
				}
				if (min > poll[i])
					min = poll[i];
			}
		}
		if (max > nBal/2)
		{
			win += can[maxIndex];
			win += "\n\n";
			return true;
		}
		else if (max == min)
		{
			for (i=0; i<nCan; i++)
			{
				if (!died[i])
				{
					win += can[i];
					win += '\n';
				}
			}
			win += '\n';
			return true;
		}
		for (i=0; i<nCan; i++)
		{
			if (!died[i] && min == poll[i])
				died[i] = 1;
		}
	}
	return false;
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0878 sec