U116660 【第十届蓝桥杯省赛】评选最佳品牌题解

ZeroMax · 2020-06-16 00:40:42 · 个人记录

该题题目较复杂，建议多读几遍题，搞懂题意和样例。

题目

题目链接：题目链接https://www.luogu.com.cn/problem/U116660

题面

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 的数字字符串，每个字符串表示一个评委的评选态度。

输出格式

评选结果。

解析：

现仅提供最基础的暴力枚举解法。

解法一（暴力枚举）：

根据题目描述枚举每种情况。

该题需注意的坑较多，下面列举题目中的“坑”：

题目中输入为不含空格的连续数字，所以输入要特殊处理，比如采用字符串形式输入。
注意结果有两种状态，评选成功和评选失败，评选成功输出胜出品牌编号，评选失败输出最后一次最少得票数的相反数
注意0为弃权，0后数据不需要记录
每轮的最小得票数的产品可能有多个，淘汰产品时需要注意处理，投票轮数也不一定是n-1轮
注意之前被淘汰的产品是不会进入之后的评判及比较的

下附带解析AC代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a/*评委人数*/,b/*产品数目*/,n/*临时记录字符串长度*/,num/**/,min_vote=0x3f3f3f3f/**/;
    char intention[1111][11];//记录评委投票意向（因输入为一串没有空格的数字，故采用char型进行输入） 
    bool vis[1111];//标记数组，标记下标为i的产品是否被淘汰，true表示被淘汰，false表示未被淘汰 
    int vote[11]={};//记录每个产品的票数 
    cin>>b>>a;
    num=b;
    for(int i=0;i<a;i++){
        cin>>intention[i];//因输入为一串没有空格的数字，故每一行以字符串的形式输入 
        n=strlen(intention[i]);
        for(int j=0;j<n;j++){//单字符变为数字
            intention[i][j]-='0';//为方便处理，这里将单字符变为数字（因字符本质是数字，所以可以继续将对应整数存入其中） 
        }
    }

    while(num>1){//投票轮数不固定，但知道剩余人数大于1是仍会继续投票 
        for(int i=1;i<=b;i++){//数组初始化，或可写成 memset(vote,0,sizeof(vote));
            vote[i]=0;
        }
        min_vote=0x3f3f3f3f;//初始化最小票数 

        //模拟评委投票的过程 
        for(int i=0;i<a;i++){//枚举每一位评委 
            for(int j=0;j<b;j++){//枚举每一件产品 
                if(intention[i][j]==0)break;//如果当前为0，表示该评委弃权，跳出当前评委的循环 
                if(vis[intention[i][j]]==false){//如果当前产品未被淘汰， intention[i][j]表示评委的投票的产品 
                    vote[intention[i][j]]++;//对应票数自增1 
                    break;  
                }
            }
        }

        //找到未被淘汰的商品中的最小票数 
        for(int i=1;i<=b;i++){
            if(vis[i]==true){//如果该产品被淘汰，跳过 
                continue;
            }
            min_vote=min(min_vote,vote[i]);//在未被淘汰的商品中占到最小票数 
        }

        //将得票数最少的产品淘汰。因得票最少的产品可能不唯一，故此处必须写循环 
        for(int i=1;i<=b;i++){
            if(vote[i]==min_vote){//如果当前产品的票数最少 
                vis[i]=true;//标记该产品为淘汰状态 
                num--;//产品数量较少1 
            }
        }
    }
    if(num==1){//如果仍有一件产品未被淘汰，即胜出 
        for(int i=1;i<=b;i++){//找到该见商品并输出 
            if(vis[i]==true){
                continue;
            }
            cout<<i;
        }
    }
    if(num==0){//如果所有产品都被淘汰，即为题目中 评选失败的情况 
        cout<<-min_vote;//输出最小得票数的相反数 
    }

    return 0;
}

U116660 【第十届蓝桥杯省赛】评选最佳品牌 题解

题目

解析：

解法一（暴力枚举）：

U116660 【第十届蓝桥杯省赛】评选最佳品牌题解