UVa 262 Transferable Voting

题目分析本题模拟了一种特殊的选举计票系统——可转移投票Transferable Voting\texttt{Transferable Voting}Transferable Voting系统。在该系统中选民需要对候选人进行排序投票然后通过多轮计票和淘汰机制来确定最终的获胜者。投票规则投票方式选民输入候选人编号111、222、333…来表示偏好顺序。例如“2 52\ 525”表示第一选择是222号候选人第二选择是555号候选人。有效选票选票上的所有数字必须是有效的候选人编号。同一数字不能重复出现。满足上述条件的选票称为有效选票否则为废票。计票规则每轮统计所有有效选票的第一选择即选票上的第一个未被淘汰的候选人。如果有候选人得票数超过有效选票总数的一半则该候选人胜出。否则淘汰得票最少的候选人可能有多个然后将这些候选人从所有选票中删除相当于将选票上后面的候选人提升到前面。重复上述过程直到产生胜者或所有候选人均被淘汰选举无结果。淘汰顺序如果一轮中有多名候选人同时被淘汰按输入中候选人出现的顺序输出淘汰信息。输入输出格式输入第一行是测试用例个数。每个测试用例包含候选人列表和选票列表两者之间有一个空行。候选人列表每行格式为“编号. 姓名”编号从111开始递增。选票列表每行是若干空格分隔的整数直到文件结束。输出每轮淘汰信息。最终结果胜者或indecisive。有效选票和废票统计。解题思路核心数据结构mapint,stringnames;// 编号 - 候选人姓名setintcandidates;// 所有候选人编号vectorvectorintballots;// 所有有效选票intspoiled;// 废票计数算法流程1. 读取候选人信息读取每行直到空行解析编号和姓名查找点号位置分割编号和姓名将编号映射到姓名同时维护候选人集合2. 读取并验证选票对于每张选票读取一行整数检查每个数字是否在候选人集合中检查是否有重复数字如果验证通过存入ballots否则spoiled3. 计票与淘汰循环while(true){// 统计当前所有有效选票的第一选择mapint,intcounter;for(autoballot:ballots){if(!ballot.empty()){counter[ballot.front()];}}// 计算最小得票和最大得票intminCounterballots.size(),maxCounter0;for(autop:counter){minCountermin(minCounter,p.second);maxCountermax(maxCounter,p.second);}// 检查是否有胜者得票超过一半if(maxCounterballots.size()/2){// 输出胜者break;}// 找出所有得票最少的候选人vectorinteliminated;for(autop:counter){if(p.secondminCounter){eliminated.push_back(p.first);candidates.erase(p.first);// 从所有选票中删除该候选人for(autoballot:ballots){ballot.erase(remove(ballot.begin(),ballot.end(),p.first),ballot.end());}}}// 按编号排序后输出淘汰信息sort(eliminated.begin(),eliminated.end());for(intid:eliminated){coutnames[id] with counter[id] votes is eliminated.endl;}// 只剩一个候选人时自动胜出if(candidates.size()1){coutThe winner of the election is names[*candidates.begin()].endl;break;}// 没有候选人了if(candidates.empty()){tietrue;break;}}关键细节处理选票更新淘汰候选人后需要从所有选票中移除该编号后续计票时直接取front()即可获得新的第一选择。自动胜出当只剩下111名候选人时无论其得票数是否过半自动胜出。这需要特殊处理。边缘情况所有选票均为废票时有效选票数量为000按规则应宣布选举无结果。无候选人的情况输入格式错误时需注意。输出顺序淘汰信息按候选人原始输入顺序输出因此需要对编号排序。代码实现// Transferable Voting// UVa ID: 262// Verdict: Accepted// Submission Date: 2016-06-08// UVa Run Time: 0.070s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapint,stringnames;// 候选人编号到姓名的映射vectorvectorintballots;// 存储所有有效选票setintcandidates;// 当前未被淘汰的候选人集合intspoiled;// 废票数量// 核心计票函数voidvoting(){booltiefalse;// 标志选举是否无结果while(true){// 统计当前所有有效选票的第一选择得票数mapint,intcounter;for(autoicandidates.begin();i!candidates.end();i)counter[(*i)]0;for(autoiballots.begin();i!ballots.end();i)if(!(*i).empty())counter[(*i).front()];// 找出当前得票的最小值和最大值intminCounterballots.size(),maxCounter0;for(autoicounter.begin();i!counter.end();i){minCountermin(minCounter,(*i).second);maxCountermax(maxCounter,(*i).second);}// 如果有候选人得票超过有效票数的一半胜出if(maxCounterballots.size()/2){for(autoicounter.begin();i!counter.end();i)if((*i).secondmaxCounter){coutThe winner of the election is ;coutnames[(*i).first].endl;break;}break;}// 找出得票最少的候选人可能有多人vectorinteliminated;for(autoicounter.begin();i!counter.end();i)if((*i).secondminCounter){eliminated.push_back((*i).first);candidates.erase((*i).first);// 从所有选票中移除被淘汰的候选人for(autojballots.begin();j!ballots.end();j)for(intk(*j).size()-1;k0;k--)if((*j)[k](*i).first)(*j).erase((*j).begin()k);}// 按候选人原始顺序编号顺序输出淘汰信息sort(eliminated.begin(),eliminated.end());for(inti0;ieliminated.size();i){coutnames[eliminated[i]] with ;coutcounter[eliminated[i]] votes is eliminated.endl;}// 如果只剩一名候选人他自动胜出无论得票数多少if(candidates.size()1){coutThe winner of the election is ;coutnames[*(candidates.begin())].endl;break;}// 没有候选人了选举无结果if(candidates.empty()){tietrue;break;}}// 输出最终结果if(tie)coutThe election was indecisive.endl;coutThere were ballots.size() valid ballots and ;coutspoiled spoiled ballots.endl;}intmain(intargc,char*argv[]){string line;intcases(getline(cin,line),stoi(line));// 读取测试用例个数// 读取第一个空行getline(cin,line);while(cases--){// 读取候选人列表names.clear();candidates.clear();ballots.clear();while(getline(cin,line),line.length()0){intindexline.find(.);intnumberstoi(line.substr(0,index));string nameline.substr(index2);names.insert(make_pair(number,name));candidates.insert(number);}// 读取选票列表spoiled0;while(getline(cin,line)){if(line.length()0){istringstreamiss(line);vectorintaBallot;setintexisted;intnumber;boolis_spoiledfalse;while(issnumber){// 检查候选人编号是否有效且未重复出现if(candidates.count(number)0existed.count(number)0){aBallot.push_back(number);existed.insert(number);}else{is_spoiledtrue;break;}}if(is_spoiledfalse)ballots.push_back(aBallot);elsespoiled;}elsebreak;}// 处理只有一名候选人的特殊情况if(ballots.size()0names.size()1){coutThe winner of the election is ;cout(*(names.begin())).second.endl;coutThere were 0 valid ballots and spoiled;cout spoiled ballots.endl;}elsevoting();// 测试用例之间输出空行if(cases)coutendl;}return0;}复杂度分析时间复杂度每轮淘汰至少一名候选人最多nnn轮nnn为候选人数。每轮遍历所有有效选票最多100010001000张和每张选票上的偏好最多nnn个总体复杂度为O(n2⋅m)O(n^2 \cdot m)O(n2⋅m)其中mmm为选票数。在题目限制下完全可以接受。空间复杂度O(n⋅m)O(n \cdot m)O(n⋅m)存储所有选票信息。