My Cow Ate My Homework

My Cow Ate My Homework ⁡ operatorname{My Cow Ate My Homework} My Cow Ate My Homework

题目链接： luogu P4086 ⁡ operatorname{luogu P4086} luogu P4086 / nowcoder 24087 ⁡ operatorname{nowcoder 24087} nowcoder 24087

题目

题目大意

在你的历史课上，你得到了一个很长的作业。这个作业包含了 N N N 个题目（ 3 ≤ N ≤ 100 , 000 3 ≤ N ≤ 100,000 3≤N≤100,000），每个题目的成绩在 0 ∼ 10 , 000 0sim 10,000 0∼10,000 之间。

按照惯例，你的老师按照以下方式计算最终成绩：去掉你最低的一个成绩，然后将其余成绩的平均成绩作为最终成绩。但不幸的是，你的宠物牛“贝西”刚刚吃了前 K K K 个题目的答案！（ 1 ≤ K ≤ N − 2 1 ≤ K ≤ N-2 1≤K≤N−2）

经过你的一番解释，老师终于相信了你的故事，并且同意对你有答案的题目（没有被吃掉答案的题目）像之前一样给分——通过去掉最低的成绩（如果有多个最低成绩，则只去掉其中一个）并取剩余成绩的平均成绩。

根据这一成绩计算方案，请按升序输出所有可以使你最终成绩最高的 K K K 的值。

样例输入

5 3 1 9 2 7 12

样例输出

2 1

思路

这道题是一道模拟。

就枚举奶牛吃掉了前面多少的，然后维护处当时你的分数。
然后找到所有最大的即可。

代码

#include<cstdio> #include<iostream> using namespace std; int n, a[100001], minn[100001], sum[100001], maxx[100001]; double maxn; int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sum[n] = minn[n] = a[n];for (int i = n - 1; i >= 1; i--) {minn[i] = min(minn[i + 1], a[i]);sum[i] = sum[i + 1] + a[i];}for (int i = 2; i < n; i++) {//枚举从第几个开始没有被吃if (1.0 * (sum[i] - minn[i]) / (double)(n - i) > maxn) {maxn = 1.0 * (sum[i] - minn[i]) / (double)(n - i);maxx[0] = 1;maxx[1] = i - 1;}else if (1.0 * (sum[i] - minn[i]) / (double)(n - i) == maxn) maxx[++maxx[0]] = i - 1;}for (int i = 1; i <= maxx[0]; i++) printf("%dn", maxx[i]);return 0; }