平均值(水题???)
今天刷题时发现了一道十分难简单的题。大家仔细看看题目。
题目
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阶恒星系”,也是这样子滴!!!
相关文章:
平均值(水题???)
今天刷题时发现了一道十分难简单的题。大家仔细看看题目。 题目 5. K11937 平均值 题目描述 在演讲比赛中,当参赛者完成演讲时,评委会对他的表演进行评分。工作人员会去掉一个最高分,一个最低分,然后计算其余的平均值作为参赛者…...
免费开源!DBdoctor推出开源版系统诊断工具systool
前言 在开发和运维过程中,经常会遇到难以定位的应用问题,我们通常需要借助Linux系统资源监控工具来辅助诊断。然而,系统的IO、网络、CPU使用率以及文件句柄等信息通常需要通过多个独立的命令工具来获取。在没有部署如Prometheus这样的综合…...
Bufferevent and SSL
bufferevent可以使用OpenSSL库实现SSL/TLS安全传输层。因为很多应用不需要或者不想链接OpenSSL,这部分功能在单独的libevent_openssl库中实现。未来版本的libevent可能会添加其他SSL/TLS库,如NSS或者GnuTLS,但是当前只有OpenSSL。 OpenSSL功能…...
我要成为算法高手-位运算篇
目录 1. 判断字符是否唯一2. 消失的数字3. 两整数之和4. 只出现一次的数字II5. 消失的两个数字 前情提要:如果对一些常见的二进制位运算不熟悉,请看这篇文章: 常见的位运算 1. 判断字符是否唯一 面试题 01.01. 判定字符是否唯一 - 力扣&…...
分布式IO模块:智慧楼宇的“智慧眼”与“智慧手”
在现代化的城市建设中,智慧楼宇作为一种集成了建筑、通信、计算机和控制等多方面技术的新型建筑,正逐渐成为城市发展的重要驱动力。智慧楼宇不仅提高了建筑设备的运行效率,降低了能源消耗,还提供了更加安全、舒适和便捷的生活办公…...
嵌入式八股文
硬件 1.CPU、MPU、MCU、SOC联系与差别 Cpu是一台计算机的运算核心和控制核心。CPU由运算器、控制器和寄存器及实现它们之间联系的数据、控制及状态的总线构成。差不多所有的CPU的运作原理可分为四个阶 段:提取(Fetch)、解码(Dec…...
【IOS】Undefined symbol: _OBJC_CLASS_$_PAGFile
项目场景: flutter构建framework包,ios导入时,报PAG动画第三方库引用错误问题。 问题描述 Undefined symbol: _OBJC_CLASS_$_PAGFile Undefined symbol: _OBJC_CLASS_$_PAGPlayer Undefined symbol: _OBJC_CLASS_$_PAGSurface 1.第三方PAG…...
Spring Boot整合Tomcat底层源码分析
引言 Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置和起步依赖等特性,大大简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring…...
工具类-基于 axios 的 http 请求工具 Request
基于 axios 的 http 请求工具 基于 axios 实现一个 http 请求工具,支持设置请求缓存和取消 http 请求等功能 首先实现一个 简单的 http 请求工具 import axios, {AxiosError,AxiosInterceptorManager,AxiosRequestConfig,AxiosResponse, } from axios;// 接口返回…...
WPF的基础控件详解
WPF的基础控件详解 在WPF学习中 基本控件是最简单也是最基础的东西。也是很初学者容易忽略的 本此笔记教程主要针对WPF中基础控件使用和应用进行手把手教学,如果学习了此笔记对你有帮助记得一键三连哦~~~~ TextBlock 基本用法 长字串处理 LineBreak标籤在指定的地…...
qt学习:截图+键盘事件
效果 生成一个透明无边框全屏的窗口,然后按ctrlb键就可以选择区域进行截图保存 步骤 新建一个项目新建一个ctrlb类继承QMainWindow新建一个CaptureScreen类继承QWidget在main中启动ctrlb类 代码 ctrlb类.cpp #include "ctrlb.h" #include "cap…...
Scala中Arry
import scala.collection.mutable.ArrayBuffer //Arry:数组 //可修改的:ArryBuffer //不可修改的:Arryobject Test_1118_2 {//可修改的:ArrayBufferdef main(args: Array[String]): Unit {//1.新建val arr1ArrayBuffer(1,2,3)//2.添加arr14a…...
学习threejs,使用AnimationMixer实现变形动画
👨⚕️ 主页: gis分享者 👨⚕️ 感谢各位大佬 点赞👍 收藏⭐ 留言📝 加关注✅! 👨⚕️ 收录于专栏:threejs gis工程师 文章目录 一、🍀前言1.1 ☘️THREE.AnimationMixer 动画…...
两大新兴开发语言大比拼:Move PK Rust
了解 Move 和 Rust 的差异有助于开发者根据项目的具体需求选择最合适的语言。选择不恰当的语言可能会导致项目后期出现技术债务。不同语言有其独特的优势。了解 Move 和 Rust 的差异可以帮助开发者拓展技术视野,发现不同语言在不同领域的应用潜力。 咱们直奔主题&a…...
基于一种基于OCR图像识别技术的发票采集管理系统及方法
本发明涉及了一种基于OCR图像识别技术的发票采集管理系统及方法,该系统的发票信息采集单元采集发票图片信息数据,OCR图像识别单元基于OCR图像识别技术并结合人工智能深度学习算法对发票图片信息数据进行识别读取以获得OCR图像识别结果,发票信…...
基于深度学习的车牌检测系统的设计与实现(安卓、YOLOV、CRNNLPRNet)+文档
💗博主介绍💗:✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示:文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…...
JavaWeb——JS、Vue
目录 1.JavaScript a.概述 b.引入方式 c.JS的基础语法 d.JS函数 e.JS对象 f.JS事件监听 2.Vue a.概述 b.Vue常用指令 d.生命周期 1.JavaScript a.概述 JavaScript是一门跨平台、面向对象的脚本语言。是用来控制网页行为的,它能使网页可交互。JavaScript和…...
Springboot 整合 Java DL4J 构建股票预测系统
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/literature?__c1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,…...
ATmaga8单片机Pt100温度计源程序+Proteus仿真设计
目录 1、项目功能 2、仿真图 3、程序 资料下载地址:ATmaga8单片机Pt100温度计源程序Proteus仿真设计 1、项目功能 设计Pt100铂电阻测量温度的电路,温度测量范围是0-100摄氏度,要求LCD显示。画出电路图,标注元器件参数&am…...
FPGA通过MIPI CSI-2发送实时图像到RK3588,并HDMI显示
介绍FPGA通过MIPI CSI-2发送实时图像到RK3588,并HDMI显示。 FPGA本地产生动态图像模板,通过MIPI CSI-2接口发送到RK3588 MIPI CSI接口。RK3588注册成相机后,调用接口并在HDMI显示器上显示。 1、RK3588驱动调试 查看Media controller信息 Med…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
