当前位置: 首页 > article >正文

平均值(水题???)

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


 题目

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阶恒星系”,也是这样子滴!!!


http://www.kler.cn/a/398288.html

相关文章:

  • [Android]相关属性功能的裁剪
  • ElasticSearch学习笔记二:使用Java客户端
  • 环境贴图选用方式
  • 计算机网络WebSocket——针对实习面试
  • 【Docker容器】一、一文了解docker
  • 数仓建设之Oracle常见语法学习
  • STM32——外部中断
  • 【C语言】连接陷阱探秘(2):命令冲突与static修饰符
  • 【Python系列】Python中打印详细堆栈信息的技巧
  • Synchronized原理
  • K8S单节点部署及集群部署
  • PyTorch 张量的常用 API
  • Guava Cache
  • SQLI LABS | Less-51 GET-Error Based-ORDER BY CLAUSE-String-Stacked Injectiion
  • 图像分割——Hough变换检测法
  • C语言——判断是不是字母
  • YOLOv7-0.1部分代码阅读笔记-train.py
  • SQLite 安装指南
  • MAC上的Office三件套报53错误解决方案(随笔记)
  • 【MogDB】MogDB5.2.0重磅发布第八篇-支持PLSQL编译全局缓存
  • 如何在 Ubuntu 上安装 Mattermost 团队协作工具
  • 【ArcGIS微课1000例】0127:计算城市之间的距离
  • 9.2 使用haarcascade_frontalface_default.xml分类器检测视频中的人脸,并框出人脸位置。
  • 企业项目级IDEA设置类注释、方法注释模板(仅增加@author和@date)
  • 你的服务器缓存中毒过么?
  • Essential Cell Biology--Fifth Edition--Chapter one (8)