自动搬运

查看原文

来自洛谷，原作者为

	liangledong 巅峰产生虚伪的拥护，黄昏见证虔诚的信徒|AFO

搬运于2025-08-24 22:32:42，当前版本为作者最后更新于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;
}