放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

UVa Q10142: Australian Voting

模拟类。本来是挺简单的,但是有几个地方没想明白,所以Wrong answer了好久。跟丫拼了,写了个测试用例生成程序,生成了一堆用例,逐一检验,终于AC了。至此《挑战编程-程序设计竞赛训练手册》第一章习题(UVa中文翻译)解答完毕,等全部AC了再做个索引目录吧。

Q10142: Australian Voting

澳大利亚在选举的时候,他们要求投票者在选票上将候选人做一个排名的动作。一开始先计算所有选票中的“第一选择”,如果有某位候选人在此时获得过半(50%)的选票,那么这位候选人立即当选。如果没有任何候选人获得过半的选票,那么票数最少的所有候选人将被排除当选资格,那些原本选择这些候选人的选票,则依照顺位将票投给下一个仍未出局的候选人。这个流程不断的重复(每一次的计票,票数最少的那些候选人都被排除当选),直到有一位候选人得到超过50%的选票或者是所有剩下的候选人得票数相同才停止。

Input

输入的第一列和第一笔测试资料之间,以及连续两笔测试资料之间都包含了一列空白。

输入的第一列有一个整数 n (n<=20)代表候选人的个数。接下来的 n列每一列依序表示了候选人的名字。这些名字可能长达80个可印出的字元。

然后会有至多1000列,每一列包含了一张选票的内容。每一张选票都包含了一个1~n的排列,第一个数代表这张选票上的“第一选择”,第二个数字代表第二顺位…以此类推。

Output

对于任两笔连续的测试资料中间请输出一列空白。

对每一组测试资料输出赢得选举的候选人名字,或是同时打成平手的所有候选人名字。

Sample Input Sample Output
1

3
John Doe
Jane Smith
Sirhan Sirhan
1 2 3
2 1 3
2 3 1
1 2 3
3 1 2
John Doe

简体中文由Lucky貓的 UVA(ACM)園地转换。

我的解法,很长很罗嗦,老实说,这是我写过的最丑的代码。

12880877    10142    Australian 
Voting    Accepted    C++    0.666    2013-12-22 16:55:32
#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

struct Person
{
	string name;
	int votes;
	int index;
};

struct Ticket
{
	int vote[20];
};

bool compare_person(const Person& p1, const Person& p2)
{
	return p1.votes > p2.votes;
}

void dump_list(const vector<Person>& list_person)
{
	return;
	for (vector<Person>::const_iterator it = list_person.begin(); it != list_person.end(); ++it)
	{
		cout << it->name << " " << it->votes << endl;
	}
	cout << "-----------" << endl;
}

void vote_for(vector<Person>& list_person, const int& index)
{
	for (vector<Person>::iterator it = list_person.begin(); it != list_person.end(); ++it)
	{
		if (it->index == index)
		{
			++(it->votes);
		}
	}
}

bool is_live(vector<Person>& list_person, const int& index)
{
	for (vector<Person>::iterator it = list_person.begin(); it != list_person.end(); ++it)
	{
		if (it->index == index)
		{
			return true;
		}
	}

	return false;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n = 0;
	cin >> n;
	while (n--)
	{
		int original_person_count = 0;
		cin >> original_person_count;
		if (original_person_count == 0)
		{
			continue;
		}
		cin.ignore();
		vector<Person> list_person(original_person_count);
		vector<Ticket> list_tickets;
		string line;
		for (int i = 0; i < original_person_count; ++i)
		{
			getline(cin, line);
			Person p;
			p.name = line;
			p.votes = 0;
			p.index = i;
			/*cout << p.name << endl;*/
			list_person[i] = p;
		}
		while (getline(cin, line) && line.length() > 0)
		{
			istringstream stream(line);
			Ticket t;
			
			for (int i = 0; i < original_person_count; ++i)
			{
				stream >> t.vote[i];
				/*cout << t.vote[i];*/
				--t.vote[i];
			
			}
		
			list_tickets.push_back(t);
			/*cout << endl;*/
		}
	
		int size = list_tickets.size();
		for (int i = 0; i < size; ++i)
		{
			Ticket t = list_tickets[i];
			vote_for(list_person, t.vote[0]);
		}
 		dump_list(list_person);
		while (true)
		{
			int max_vote = 0, min_vote = list_person.begin()->votes;
			for (vector<Person>::const_iterator it = list_person.begin(); it != list_person.end(); ++it)
			{
				if (it->votes > max_vote)
				{
					max_vote = it->votes;
				}
				else if (it->votes < min_vote)
				{
					min_vote = it->votes;
				}
			}
			
			if (max_vote * 2 > list_tickets.size())
			{
				// 得票过半,结束

				if (list_person.size() > 1)
				{
					for (vector<Person>::iterator it = list_person.begin(); it != list_person.end();)
					{
						if (it->votes < max_vote)
						{
							it = list_person.erase(it);
						}
						else
						{
							++it;
						}
					}
				}
 				dump_list(list_person);
				break;
			}
			else if (max_vote == min_vote)
			{
				// 所有人得票一样,结束
 				dump_list(list_person);
				break;
			}
			else
			{
				// 最后那几个个人出局
				// 出局的人的id
				vector<int> out_list;

				for (vector<Person>::iterator it = list_person.begin(); it != list_person.end();)
				{
					if (it->votes == min_vote)
					{
						out_list.push_back(it->index);
						it = list_person.erase(it);
					}
					else
					{
						++it;
					}
				}

				// 每出局一个人,原来投给他的票必须重新计算
				for (vector<int>::const_iterator it_out = out_list.begin(); it_out != out_list.end(); ++it_out)
				{
					for (vector<Ticket>::iterator it = list_tickets.begin(); it != list_tickets.end(); ++it)
					{
						Ticket t = *it;
						for (int position = 0; position < original_person_count; ++position)
						{
							if (is_live(list_person, t.vote[position]))
							{
								break;
							}
							if (t.vote[position] == *it_out)
							{
								for (position = position + 1; position < original_person_count; ++position)
								{
									if (is_live(list_person, t.vote[position]))
									{
										vote_for(list_person, t.vote[position]);
// 										cout << "投给" << *it_out + 1 << "的票" << t.vote[0] + 1 << " " << t.vote[1] + 1 << " " << t.vote[2] + 1 << " " << t.vote[3] + 1 << " "
// 											<< "要重投给" << t.vote[position] + 1 << endl;
										dump_list(list_person);
										break;
									}
								}
								break;
							}
							else if (find(out_list.begin(), out_list.end(), t.vote[position]) != out_list.end())
							{
								break;
							}
						}
					}
				}
			}
		}

		for (vector<Person>::const_iterator it = list_person.begin(); it != list_person.end(); ++it)
		{
			cout << it->name << endl;
		}
		if (n && list_person.size())
		{
			cout << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » UVa Q10142: Australian Voting

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机