平均值(水题???)
今天刷题时发现了一道十分难简单的题。大家仔细看看题目。
题目
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阶恒星系”,也是这样子滴!!!