UVA10142/PC110108Australian Voting
| 10142 | Australian Voting | Accepted | C++11 | 0.769 | 2014-02-11 05:01:20 |
这题目感觉上思路很多，但是因为有一些想法上的缺陷，困扰了我好长一段时间，可能是刚刚入门的原因。
从理解题目就很坑爹了，如果你跟我一样是用刘汝佳的编程挑战的话。
题目的意思就是：
有n个候选人，以及选票（个数不会在输入时候事先给定），每个选票是一个序列，我们每次只读取第一个未出局的。
结束只有两种可能：
一、获票最高者所得票大于总票数的一半
二、所有人票都相同
那么在处理好读人名和票数据后，很容易就知道怎么写了。
我的思路就是：得到总票数pnum,最大票数maxs，最小票数mins，以及最大票数的下标maxi，
对于第一种情况，直接判断maxs>pnum/2;之后再利用下标输出其名字。
对于第二种情况，直接比较maxs==mins,即可。（夹逼定理）
对于淘汰，则让候选人的票数为-6，当然，这个只要是个负数即可。
关键：最后一个案例不要输出换行。
我的测试数据：(仅仅供给参考。)
4 3
a
b
c
1 2 3 4
a
b
c
d
1 2 3 4
1 2 3 4
1 2 3 4
2 1 3 4
2 1 3 4
2 1 3 4
3 4 1 2
3 4 2 1 4
a
b
c
d
1 2 3 4
1 2 3 4
1 2 3 4
2 1 3 4
2 1 3 4
2 1 3 4
3 4 1 2
我的代码。
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <sstream>
using namespace std; int main()
{ vector<string> n;
vector<int> s;
map<int,vector<int> > p;
string tmp;
int cases; //案例个数
int mnum; //候选人个数
int i;
cin>>cases;
while(cases--){
n.clear();
p.clear();
s.clear();
cin>>mnum;
if(mnum){
cin.ignore();
n.resize(mnum+1);
s.resize(mnum+1);
int pnum=0; //票数 vector<int>::iterator itr; for(i=1;i<=mnum;i++){
getline(cin,tmp);
n[i]=tmp; } while((getline(cin, tmp), tmp.length() > 0)) {
//读票
vector<int> ptmp(mnum);
istringstream iss(tmp); for(i=0;i<mnum;i++)
iss>>ptmp[i]; p[pnum]=ptmp;
pnum++; } //选举
for(i=0;i<pnum;i++){
itr=p[i].begin();
s[*itr]++; } //得出结果
while(1){ /*
for(i=1;i<=mnum;i++){
cout<<n[i]<<" "<<s[i]<<endl; //选票过程 }
*/
int maxs=-1,mins=5000,maxi=-1;
//选最大最小
for(i=1;i<=mnum;i++){
if(s[i]>=0){
if(s[i]>maxs){
maxs=s[i];
maxi=i;
}
if(s[i]<mins){
mins=s[i];
}
} } //1.最高者大于50%
if(maxs>pnum/2){
cout<<n[maxi]<<endl;
break;
}
//2.平局
if(maxs==mins){
for(i=1;i<=mnum;i++){
if(s[i]>0){
cout<<n[i]<<endl;
}
}
break; }
//cout<<mins<<"mins"<<endl;
//3.未定
//线性搜索出s[i]==min的出来;
for(i=1;i<=mnum;i++){
if(s[i]==mins){
s[i]=-6; //随便设定一个负数，以表示出局; }
} for(i=0;i<pnum;i++){
itr=p[i].begin();
if(s[*itr]==-6){
while(s[*itr]==-6){
// tt.push(i);
itr=p[i].erase(itr);
}
s[*itr]++;
}
}
} if(cases!=0)
cout<<endl;
}
} return 0;
}