A50861. 评选最佳品牌n 个评委投票，在 m 个商品中评选一个最佳品牌。评选采用多轮淘汰制，即：每轮投票，淘汰掉得票最少的候选品牌（得票并列最少的品牌一起淘汰）。如此一轮轮淘汰下去，如果最后只剩下一个品牌当选，即告评选成功。但如果在某轮投票中，当时未被淘汰的所有候选品牌（大于等于两个品牌）都并列得票最少，即告评选失败。如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。在评选流程中，每…
填空题
较难
知识点
题目描述
评选最佳品牌
n 个评委投票，在 m 个商品中评选一个最佳品牌。
评选采用多轮淘汰制，即：每轮投票，淘汰掉得票最少的候选品牌（得票并列最少的品牌一起淘汰）。
如此一轮轮淘汰下去，如果最后只剩下一个品牌当选，即告评选成功。
但如果在某轮投票中，当时未被淘汰的所有候选品牌（大于等于两个品牌）都并列得票最少，即告评选失败。
如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。
在评选流程中，每个评委的态度都可用一个序列来表示；例如当 m=5 时，某评委的评选态度序列为：3、
5、1、2、4，则表示该评委：优先投 3 号，当 3 号被淘汰时投 5 号，当 3 和 5 都被淘汰时投 1，当 3、5、1 都被淘汰时投 2，仅剩 4 号时才投 4 号品牌的票。
选票的序列中可以表示弃权，用 0 来表示，例如当 m=5 时，某评委的评选态度序列为：3、5、0，则表示该评委：优先投 3 号，当 3 号被淘汰时投 5 号，其它情况下不投任何品牌的票。
编程实现：
请你编一个程序，模拟各轮投票的过程，得到评选结果。
输入：
第一行：m(0<m<10,表示参加评选的品牌数)和 N(1<n<1000,表示参加投票的评委数)，之间以空格分隔接下来的 n 行：每行都是长度不超 m 的数字字符串，每个字符串表示一个评委的评选态度。
输出：
评选结果。
样例 1 输入：
3 4
123
213
132
10样例 1 输出：
1样例 2 输入：
3 4
321
213
231
312样例 2 输出：
-2参考答案
#include<iostream>
#include<algorithm>
#include<cstring>
#include<fstream>
using namespace std;
const int M=15,N=1010;
int g[N][M];//存储评委投票态度
int piao[M];//得票桶
int st[M];//品牌标识桶
bool success=true;
int last_piaoshu;
int last_pinpai;
int n,m;//n个评委 m个品牌
void pingxuan()
{
while(1){
memset(piao,0,sizeof(piao));
for(int i=1;i<=n;i++)
for(int j=1;j<M;j++){
int k=g[i][j];
if(k==0) break;//弃权票
if(st[k])continue;//品牌已淘汰
piao[k]++;//投票入桶
break;//投票完成换下个评委
}
//寻找最大票数和最小票数
int min=1001,max=-1001;
for(int i=1;i<M;i++){
if(piao[i]<min && !st[i])min=piao[i];
if(piao[i]>max && !st[i])max=piao[i];
}
if(max>min){//淘汰掉最小得票的品牌
for(int i=1;i<M;i++)
if(piao[i]==min && st[i]==false)st[i]=true;//标志淘汰
continue;//进入下一轮评选
}
else{
int sum=0;
for(int i=1;i<M;i++)//搜索有几个最小票数的品牌
if(piao[i]==min)sum++,last_pinpai=i;
if(sum==1)return;//只剩一个品牌，结束循环
else{//剩余多个品牌，评选失败
last_piaoshu=min;//保留最后一轮的得票
success=false;//标识失败
return ;//评选结束 退出循环
}
}
}
}
int main()
{
//freopen("king.in","r",stdin);
cin>>m>>n;
for(int i=1;i<=n;i++){
string str;
cin>>str;
for(int j=0;j<str.size();j++)
g[i][j+1]=str[j]-'0';
}
pingxuan();
if(success) cout<<last_pinpai<<endl;
else cout<<"-"<<last_piaoshu<<endl;
return 0;
}答案解析
考察知识:
字符串,桶排序,模拟算法
上一题
下一题