nhoi2004求解

Question

班委会选举(nhoi2004xx4)

信息学夏令营开营了，OI⑸班要进行班委会选举，需要选出正班长、副班长、学习委员、文娱委员和纪律委员各一名。选举办法如下：
⑴先由全班同学推出8名候选人，其中女生至少２名；
⑵将候选人分别编号为１、２、３、４、５、６、７、８，由全班同学投票，票上只填写被选举人的编号，填写小于3人或大于5人以及填写编号不在1—8范围内的票视为无效票不予统计。
⑶投票结束后通过统计票数确定各职务名单。原则上按得票数从高到低分别选为正班长（ZhengBZ）、副班长(FuBZ)、学习委员(XuexiWY)、文娱委员(WenyuWY)和纪律委员(JilvWY)，票数相同者按编号优先，但若有女生得票在前五名，则文娱委员必须由得票最多的女生担任。
⑷另外，选举规定：当有效票数不超过半数（表示为“A”）或不足５人得票(表示为“B”)时，宣布本次选举无效。
已知班干部候选名单如下：
image.png

假定除了前述说明外，不会出现其它不合要求的选票。请你编一个程序，帮助OI⑸班选出班干部名单。

输入描述

第一行输入OI⑸班人数 N （8 <= N <= 50 ）,
第二行到第N+1行分别输入每位同学的选票数据。

输出描述

按职务顺序输出班干部名单。若是选举无效，则输出无效原因代码及“Wu Xiao”，属“A”的还要输出有效票数，属“B”的要输出得票人数。

用例输入 1

10
123
1234
12345
48
23567
3678
1467
12368
2
1239
用例输出 1

Li Chen Wang Liu Pan
用例输入 2

12
2387
269
458
2
56
72
8
9
3682
456273
15
483
用例输出 2

A:Wu Xiao 4

#include<bits/stdc++.h>
#define happy using namespace std;
#define end return 0;
#define main int main()
#define ll long long
#define sc scanf
#define pr printf

happy
ll g,yes=0,a[105],rs=0,len=0,f,n=0,k;
string st,name[9]={" ","Li","Chen","Liu","Pan","Deng","Wang","Lu","Gao"};
ll sex[9]={0,0,0,1,0,0,0,0,1},bh[15];
main
{
    sc("%lld",&g);
    n=g;
    while(g--)
    {
        cin>>st;
        f=0;
        len=st.size();
        if(len<3||len>5)continue;
        for(ll i=0;i<len;i++)
        {
            if(st[i]<'1'||st[i]>'8'){f=1;break;}
        }
        if(f==1)continue;
        yes++;
        for(ll i=0;i<len;i++)a[st[i]-'0']++;
    }
    if(yes<=n/2)
    {
        pr("A:Wu Xiao ");
        pr("%lld",yes);
        return 0;
    }
    for(ll i=1;i<=8;i++)
    {
        if(a[i]>0)rs++;
        bh[i]=i;
    }
    if(rs<5)
    {
        pr("B:Wu Xiao ");
        pr("%lld",rs);
        return 0;
    }
    for(ll i=1;i<8;i++)
    {
        for(ll j=i+1;j<=8;j++)
        {
            if(a[i]<a[j]||a[i]==a[j]&&bh[i]>bh[j])
            {
                swap(a[i],a[j]);
                swap(bh[i],bh[j]);
                swap(sex[i],sex[j]);
                swap(name[i],name[j]);
            }
        }
    }
    for(ll i=1;i<=5;i++)
    {
        if(sex[i]==1)
        {
            k=i;
            break;
        }
    }
    if(k==5){swap(a[4],a[5]);k=4;}
    if(k==0||k==4)
    {
        for(ll i=1;i<=5;i++)cout<<name[i]<<" ";
    }
    else
    {
        for(ll i=1;i<=5;i++)
        {
            if(i==k)continue;
            cout<<name[i]<<" ";
            if(i==4)cout<<name[k]<<" ";
        }
    }
    
    end
}

Answer 1

引自免费微信小程序：皆我百晓生

解决该问题的一种方法是使用计数排序。

首先，我们定义一个长度为9的数组count，用来记录每个候选人的得票数。初始化count数组的所有元素为0。

然后，我们遍历每个选票，将有效选票对应的候选人编号在count数组中加1。

接下来，按照规则确定班干部名单。首先判断选举是否有效。如果有效票数不超过半数或不足5人，则输出无效原因代码。

如果选举有效，我们根据票数从高到低确定正班长、副班长、学习委员、文娱委员和纪律委员，考虑女生得票的情况。

最后，按照职务顺序输出班干部名单。

以下是C++示例代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

struct Candidate {
    int number;  // 候选人编号
    int votes;  // 得票数
    bool isFemale;  // 是否为女生

    Candidate(int num, int v, bool isF) : number(num), votes(v), isFemale(isF) {}
};

bool cmp(const Candidate& a, const Candidate& b) {
    if (a.votes != b.votes) {
        return a.votes > b.votes;  // 票数从高到低排序
    } else if (a.isFemale != b.isFemale) {
        return a.isFemale > b.isFemale;  // 女生得票在前
    } else {
        return a.number < b.number;  // 编号小优先
    }
}

int main() {
    int N;
    std::cin >> N;

    std::vector<Candidate> candidates;
    for (int i = 1; i <= 8; ++i) {
        candidates.push_back(Candidate(i, 0, false));
    }
    for (int i = 0; i < N; ++i) {
        int vote;
        std::cin >> vote;
        if (vote >= 1 && vote <= 8) {
            candidates[vote - 1].votes++;
        }
    }

    std::sort(candidates.begin(), candidates.end(), cmp);

    int validVotes = 0;
    int invalidReason = 0;  // 0表示选举有效
    if (N <= 8 || candidates[0].votes * 2 <= N) {
        invalidReason = 'A';
        validVotes = candidates[0].votes;
    } else if (candidates[4].votes == candidates[5].votes && candidates[5].isFemale) {
        candidates.erase(candidates.begin() + 5);
    }
    
    if (invalidReason != 0) {
        std::cout << invalidReason << " Wu Xiao" << std::endl;
        if (invalidReason == 'A') {
            std::cout << validVotes << std::endl;
        } else {
            std::cout << candidates.size() << std::endl;
        }
    } else {
        std::cout << "ZhengBZ: " << candidates[0].number << std::endl;
        std::cout << "FuBZ: " << candidates[1].number << std::endl;
        std::cout << "XuexiWY: " << candidates[2].number << std::endl;
        std::cout << "WenyuWY: " << candidates[3].number << std::endl;
        std::cout << "JilvWY: " << candidates[4].number << std::endl;
    }

    return 0;
}

在上述代码中，我们使用了一个结构体Candidate来存储候选人的编号、得票数和是否为女生。cmp函数用于比较两个Candidate对象的大小，按照题目规则确定候选人排序。

主函数中，我们首先读入班级人数N，然后初始化候选人列表candidates，并遍历选票统计得票数。

接着，我们使用std::sort函数对候选人列表以cmp函数为比较准则进行排序。

然后，我们根据选举的有效性和女生得票情况，删除得票数相同并且女生得票在前的候选人。如果选举无效，输出无效原因代码及相应的数据。否则，按照职务顺序输出班干部名单。

以上就是根据问题描述提供的一种解决方案。希望对你有帮助！