自定义优定软件网站建设太原好的网站制作排名
今天刷题时发现了一道十分难简单的题。大家仔细看看题目。
题目
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阶恒星系”，也是这样子滴！！！