P7743 [COCI2011-2012#3] D’HONDT 题解

liangledong · 2023-10-18 16:48:12 · 题解

题意：

先从所有政党中选出得票数不少于总票数 5\% 的政党，再从这些政党中选出 14 个得分最多的代表，每个代表的得分分别为此政党票数的 \dfrac{1}{1},\dfrac{1}{2},\dfrac{1}{3} \dots \dfrac{1}{14}，最后按字母升序排序把每个符合条件的政党及其入选代表数输出。

思路：

先把符合条件的政党全部筛选出来，然后把每个代表的得分算出来，再从中选择 14 个得分最多的代表，计算他们对政党的贡献。具体实现请看代码。

注意：题目的除法运算可能除不尽，要使用 double 进行运算，也尽量使用乘法，减少精度损失。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,tot,t;//tot表示符合条件的政党数,t表示代表候选人人数
double x;
struct data{//存政党
    double g;
    int sum;
    char ch;
}a[19],b[19];//a存所有政党,b存符合条件的政党
struct dat{//存代表
    double s;
    int num;
}c[209];//代表总量最大值为 12*14=168
int cmp(data a,data b){
    return a.ch<b.ch;
}//按字典序排序政党
int cc(dat a,dat b){
    return a.s>b.s;
}//按分数排序代表
int main(){
    cin>>x>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].ch>>a[i].g;
        if(a[i].g*20>=x){
            b[++tot]=a[i];
            for(int j=1;j<=14;j++){
                double jj=j*1.0;
                c[++t].num=tot;
                c[t].s=b[tot].g/jj;//计算每个代表的分数
            }
        }
    }
    sort(c+1,c+1+t,cc);
    for(int i=1;i<=14;i++){
        b[c[i].num].sum++;//计算每个政党的代表人数
    }
    sort(b+1,b+1+tot,cmp);
    for(int i=1;i<=tot;i++){
        cout<<b[i].ch<<" "<<b[i].sum<<"\n";
    }
    return 0;
}