平均值(水题？？？）

 今天刷题时发现了一道十分难简单的题。大家仔细看看题目。

---

 题目

5. K11937 平均值

题目描述

在演讲比赛中，当参赛者完成演讲时，评委会对他的表演进行评分。工作人员会去掉一个最高分，一个最低分，然后计算其余的平均值作为参赛者的最终成绩。

现在给定n个正整数，去掉最大的n1个数和最小的n2数，然后计算其余的平均值

输入格式

输入包含多组测试数据，每组数据包含两个两行，第一行是三个整数n1 n2 n(1≤n1,n2≤10，n1+n2≤n≤5*10^6)

第二行是n个整数,每个整数的范围是1到10^8

当输入为一行“0 0 0”表示输入结束

输出格式

对于每组测试数据，输出平均值，结果保留6位小数

输入输出样例

输入样例1：复制

1 2 5

1 2 3 4 5

4 2 10

2121187 902 485 531 843 582 652 926 220 155

0 0 0

输出样例1：复制

3.500000

562.500000

【耗时限制】4000ms 【内存限制】10MB

注意 

 不知道大家有没有发现啊，这一题的【耗时限制】和【内存限制】有些特别。

【耗时限制】4000ms 【内存限制】10MB

4000m很大，但10MB......

我们来算算

---

10MB=10240KB≈10^7bits 一个int类型的变量占4个字节

1≤n≤5*10^6    数组要开这么大：5000000

10^7/4=2.5*10^6 只有2500000个int，况且程序运行还要空间

不说算法，开个数组就爆了好吗！！！

---

这咋写啊！！！

推算一下

 先不说超空间，来看看基本写法：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n1,n2,n,a[5000010];
int main()
{while(cin>>n1>>n2>>n&&n1+n2+n>0){for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+n+1);LL sum=0;for(LL i=n2+1;i<=n-n1;i++) sum+=a[i];printf("%.6lf\n",sum*1.0/(n-n1-n2));}return 0;
}

如果你仍然啥也看不出来

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n1,n2,n,a[5000010];
int main()
{while(cin>>n1>>n2>>n&&n1+n2+n>0){LL sum=0;for(LL i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];}sort(a+1,a+n+1);for(LL i=1;i<=n2;i++) sum-=a[i];for(LL i=n-n1+1;i<=n;i++) sum-=a[i];printf("%.6lf\n",sum*1.0/(n-n1-n2));}return 0;
}

诶，sum+=a[i]不需要排序就能直接加，也就是说，可以是这样：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n1,n2,n,a;
int main()
{while(cin>>n1>>n2>>n&&n1+n2+n>0){LL sum=0;for(LL i=1;i<=n;i++){scanf("%lld",&a);sum+=a;}//去掉最大的n1个数//去掉最小的n2个数printf("%.6lf\n",sum*1.0/(n-n1-n2));}return 0;
}

现在的问题是怎么“去掉最大的n1个数”“去掉最小的n2个数”

---

开始正片Action

 意料之外，情理之中

怎样“去掉最大的n1个数”“去掉最小的n2个数”

答案是优先队列

先来回忆一下优先队列：

->priority_queue是c++提供的一个优先队列的实现，使用二叉堆实现。<-

->priority_queue默认是大根堆， 堆顶元素即为序列中的最大<-

->priority_queue默认为大根堆，可以较方便的获取最大值，想要获取最小值时，可以将默认 的大根堆修改为小根堆。<-

->二叉堆适用于在一个动态变化的序列中查找极大值或极小值<-

->二叉堆一般应用在贪心和动态规划类问题中，用于阶段性最优值的获取。<-

欸，这和“最大的n1个数”“最小的n2个数”有什么关系？？？

其实，优先队列不仅能查找极大值或极小值，还可以维护一群最小值/最大的。

先翻到文章末尾来做个选择

---------------------------------------------------------如何实现？---------------------------------------------------------

来一个，更新一次

这是一个容器

————————

|           点赞          |

|          关注           |

————————

来了一个元素就放进去

如果元素数量比n1大了

就把最小的踢了

这样就实现了维护一群最大的

既然要“把最小的踢了”，就该用小根堆

而维护一群最小值，就该用大根堆

---

理一理：

        小根堆->(维护一群最大的/极小值)

        大根堆->(维护一群最小值/极大值)

你学废了吗？

这样这题就能这样写：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n1,n2,n,a;
priority_queue<LL> pq1;
priority_queue<LL,vector<LL>,greater<LL> > pq2;
int main()
{while(cin>>n1>>n2>>n&&n1+n2+n>0){LL sum=0;for(LL i=1;i<=n;i++){scanf("%lld",&a);pq1.push(a);pq2.push(a);sum+=a;if(pq1.size()>n2) pq1.pop();if(pq2.size()>n1) pq2.pop();}//去掉最大的n1个数while(!pq1.empty()) sum-=pq1.top(),pq1.pop();//去掉最小的n2个数while(!pq2.empty()) sum-=pq2.top(),pq2.pop();printf("%.6lf\n",sum*1.0/(n-n1-n2));}return 0;
}

---

评测结果

 

 大家可以试试“K阶恒星系”，也是这样子滴！！！