AT795题解

ZepX_D · 2021-07-19 19:00:29 · 题解

题意：

输入 n 个数，取其中任意 k 个数依次运算，使 C 尽可能大。

分析

首先我们需要进行排序,排序之后从最大数向后取 k 个数，这时问题来了，如果我们先选取最大的数进行运算，那么它的受益会大大折扣，因为它会除以 2^k ,就会导致它的收益越来越小，例： ((2+2)/2+4)/2>((2+4)/2+2)/2 所以我们应从第 k 大的数开始选取进行运算。

code

#include<cstdio>
#include<cctype>
#include<algorithm>// sort 头文件

using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))// isdigit(x) 判断是否是数字字符，需调用 cctype 库
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*f;
} 
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,k;
    double c=0;//这里要用 double
    n=read();k=read();
    int a[n+1];//节省空间
    for (int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,cmp);
    for (int i=k;i>=1;i--) c=(c+a[i])/2;//从第 k 大的数选取到最大的数
    printf("%.6lf\n",c);//保留小数点后六位
    return 0;//完美收官
}

总结

这个黄题并不难， sort 完全能过，我们只需要注意从第 k 大的数开始选取进行运算，使最大值的收益最大化，这样才能使 C 的值最大，然后就可以吊打 AC 这道题了 另：三次提交均为最优解，这里附上链接: AC

三次记录 AC