码农场
模拟类。本来是挺简单的，但是有几个地方没想明白，所以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//////////////////////////////////
