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

**题解 [P4086 【[USACO17DEC]My Cow Ate My Homework S】](https://www.luogu.com.cn/problem/P4086)** # 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)$。