一个小题解

Liquefyx · 2021-08-24 14:44:32 · 题解

这题怎么没题解啊？（这道题简简单单，只要看的懂题，懂点数学就能做啊）那就水一篇题解吧 qwq。

题目分析

这道题题目说的就很简略（虽然还有一堆没用的背景），就是求 N 个人中选若干人士贡献金钱，使得当前金钱占总金钱的百分比减去人数占总人数百分比后的值最大。

那么看懂题目后我们再进行推导。如果选了 M 个人，则人数占总人数的百分比为 A = \frac{M}{N}\%，然后计算这些人的金钱总数 S，求出当前金钱占总金钱 P_n 的百分比 B = \frac{S}{P_n}，但是这样暴力的话很麻烦，我们要想一些办法化简它。因为总人数和总金钱是固定的，我们便能想到乘法分配律，将求百分比时除的除数看成乘上这个除数的倒数，如下：

那么每个人占总人数的百分比与每个人的金钱占总金钱的百分比的分别的和就是真实的百分比 A 和 B 了。为了使 B-A 能尽量大，只需要先按每个人的金钱数排序，再判断金钱数占总金钱的百分比是否比这个人占总人数的百分比 \frac{1}{N}\% 大就可以，这样就是比较贪心的暴力。

注意：百分比 A 和 B都只输出百分数数字部分，所以说要乘一百再输出

代码呈上

#include <bits/stdc++.h>
using namespace std;
int n;
double per[300005],sum,pd,a,b;
int comp(double a,double b){
    return a > b;
}
int main(){
    scanf("%d",&n);//输入 
    pd=1.0/n;//提前算出n分之一的值,便于枚举B的值 
    for(int i = 1; i <= n; ++i)
        scanf("%lf",&per[i]), sum+=per[i];//输入并计算n个人p值总和 
    for(int i = 1; i <= n; ++i)
        per[i]=per[i]/sum;//提前除上所有人p值总和,便于计算A的值
    sort(per+1, per+1+n, comp);//从大到小排序,方便枚举 
    for(int i = 1; i <= n; ++i)
        if(per[i] >= pd)//如果添加的这个人的pi/np比1/n多,那么添加这个人后A-B的值又会多上一些 
            a+=per[i], b+=pd;
    printf("%.14lf\n%.14lf",b*100/*转为百分数*/,a*100/*转为百分数*/);//输出答案 
    return 0;
}

这样就做完啦 LOuO。