首页 > 代码库 > PAT Spring Outing
PAT Spring Outing
首先题目大意为一个班级N位同学投票春游地点，K个候选地，若某个地点投票票数大于一半人数，则选择这个地点，若所有地点都没有被选择则在家呆着。
且每个人都很聪明，投票时会做出最有利与自己的选择。
输入例子为:
2 2
1 0 2
2 1 0
第一行为N,K
下面N行K+1个数为他们的投票次序
很容易陷入一个误区，就是每个人的次序即为他们的喜好次序。
In the sample case, if the second peoson vote against the first place, no place would be selected finally because the first person must vote against the second place for his own interest. Considering staying at home is a worse choice than the first place, the second person‘s optimal strategy is voting for the first place. So the first place will be selected
这个解释给我们的最重要的信息为：against（反对）
第一个人的投票次序为1 0 2
即，第一个人宁可在家待着也不去2，即为反对。反之，在0前面的数字，即为他可接受的地点。
所以我们可以以0为分界，只要对每个人投票中，他们可接受的地点计数，第一个被选中的地点即为春游地点。
上代码
1 #include <iostream> 2 #include <vector> 3 4 using namespace std; 5 6 int selectP(int N,int K){ 7 vector<vector<int> > v; 8 v.reserve(N); //预先分配空间减少容器空间分配次数、防止空间浪费 9 int m;10 for(int i=0;i<N;++i){11 vector<int> vv;12 vv.reserve(K+1);13 for(int j=0;j<K+1;++j){14 cin>>m;15 vv.push_back(m);16 }17 v.push_back(vv); //N个人的K+1个信息都在vz中18 }19 vector<int> cont(K+1,0);20 for(int i=0;i<N;++i){21 for(int j=0;j<K+1;++j){22 if(v[i][j]>0){ //遇到0之前为每个可接受景点计数23 if(++cont[v[i][j]]>=(N/2+1)) //如果加一后大于一半人数就返回景点标号24 return v[i][j];25 }26 else27 break; //遇到0，这个人的可接受景点录完，跳出28 }29 }30 return 0;31 }32 33 int main()34 {35 int N,K;36 cin>>N>>K;37 int m = selectP(N,K);38 if(m)39 cout<<m;40 else41 cout<<"otaku";42 return 0;43 }
PAT Spring Outing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。