Voldemort's blog

Voldemort's blog

我好菜啊

题解 P4086 【[USACO17DEC]My Cow Ate My Homework S】

posted on 2020-07-05 11:16:06 | under 题解 |

题解 P4086 【[USACO17DEC]My Cow Ate My Homework S】

Description

给你一串长度为 $n$ 的数组,在去掉前 $k$ 个数字和剰下来数字中最小的数字后,将剩下来的数字求平均值,使得平均值最大,求满足条件的所有 $k$ 的值,把这些 $k$ 换行输出

Solution

这题我们考虑前缀和,设 $\text{sum}(i)$ 表示区间 $[1,i]$ 中所有数字的和, $\min(i)$ 表示区间 $[i,n]$ 之间所有数字的最小值。接下来枚举 $k$ 的所有可能取值 ,并确定 最大数字 后找到所有的 $k$ 并且输出即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1000009;
const double eps = 0.00000000000217;//确定最小精度,不然可能会出错

int sum[N],n,Min[N],a[N];
double Score,Max;

template<class T>
inline void read(T& x) {//快读
    x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
}

int main() {
    read(n);
    sum[0] = 0;Min[n + 1] = 2147483647;
    for(int i = 1;i <= n;i++) {
        read(a[i]);
        sum[i] = sum[i - 1] + a[i];//前缀和
    }
    for(int i = n;i >= 1;i--) {
        Min[i] = min(Min[i + 1],a[i]);//后缀最小值
    }
    for(int i = 1;i <= n - 2;i++) {//枚举所有满足条件的k值
        Score = (sum[n] - sum[i] - Min[i]) * 1.0 / (n - i - 1);//计算式子
        if(Score - Max >= eps) {//确定最大值
            Max = Score;
        }
    }
    for(int i = 1;i <= n - 2;i++) {
        Score = (sum[n] - sum[i] - Min[i]) * 1.0 / (n - i - 1);
        if(fabs(Score - Max) < eps) printf("%d\n",i);//找到所有的k并且输出
    }
    return 0;
}

本算法时间复杂度为 $\Theta(n)$。