排队接水--贪心
排队接水
题目描述
有 n n n 个人在一个水龙头前排队接水,假如每个人接水的时间为 T i T_i Ti,请编程找出这 n n n 个人排队的一种顺序,使得 n n n 个人的平均等待时间最小。
输入格式
第一行为一个整数 n n n。
第二行 n n n 个整数,第 i i i 个整数 T i T_i Ti 表示第 i i i 个人的等待时间 T i T_i Ti。
输出格式
输出文件有两行,第一行为一种平均时间最短的排队顺序;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
样例 #1
样例输入 #1
10
56 12 1 99 1000 234 33 55 99 812
样例输出 #1
3 2 7 8 1 4 9 6 10 5
291.90
提示
n ≤ 1000 , t i ≤ 1 0 6 n \leq 1000,t_i \leq 10^6 n≤1000,ti≤106,不保证 t i t_i ti 不重复。
当 t i t_i ti 重复时,按照输入顺序即可(sort 是可以的)
思路
要让n个人平均等待时间最小,就要让打水快的在前面。(打水快的人打完就走了,后面的人就可以不用等那么久,但是如果把打水慢的人放在前面,后面的人要等好久。),这里用的结构体来记录打水人的编号。所以总的要等的时间就是前面的人的打水时间。故对于每个前面打水的人,后面的人都要等他,所以就有sum+=water[i].tim*(n-i),最后,除以n即可。
#include<iostream>
#include<algorithm>
#include<iomanip>//保留小数函数头文件
using namespace std;
const int N=1e3+10;
struct node
{int num;int tim;
}water[N];
bool cmp(node a,node b)
{if(a.tim!=b.tim)return a.tim<b.tim;return a.num<b.num;
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){water[i].num=i;cin>>water[i].tim;}sort(water+1,water+1+n,cmp);double sum=0;for(int i=1;i<=n;i++){sum+=water[i].tim*(n-i);//总时间cout<<water[i].num<<" ";}cout<<endl<<fixed<<setprecision(2)<<sum/n<<endl;return 0;
}
相关文章:
排队接水--贪心
排队接水 题目描述 有 n n n 个人在一个水龙头前排队接水,假如每个人接水的时间为 T i T_i Ti,请编程找出这 n n n 个人排队的一种顺序,使得 n n n 个人的平均等待时间最小。 输入格式 第一行为一个整数 n n n。 第二行 n n n 个…...
数字温度传感器-DS18B20
文章目录 一、DS18B20器件图二、DS18B20特点三、DS18B20内部结构内部构成 四、工作时序1.初始化时序2.ReadOneChar2.WriteOneChar 一、DS18B20器件图 DS18B20的管脚排列: GND为电源地;DQ为数字信号输入/输出端;VDD为外接供电电源…...
【算法】【算法杂谈】从M个数中等概率的选出n个数,保证每一个数的选中概率都是n/m(蓄水池算法)
目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言 当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 问题介…...
vue3+ts+vite自适应项目——路由、layout布局
系列文章目录 第一章:搭建项目 目录 系列文章目录 前言 一、vue-router 1.安装vue-router 2.引入 2.1 新建页面 2.2 公共样式引入 2.3 layout 布局 2.4路由配置 总结 前言 上一章我们搭建了项目,这一张主要讲路由和layout布局,和…...
数据库之约束、索引和事务
一、约束 约束,顾名思义就是数据库对数据库中的数据所给出的一组检验规则.负责判断元素是否符合数据库要求.其目的就是为了提高效率以及准确性. 1.not null - > 数据元素非空 表示如果插入数据,则当前数据不能为空. //创建一张学生表,其班级id和年级id不为空 create …...
centos --libreoffice使用
您可以按照以下步骤在CentOS上安装LibreOffice: 打开终端并使用root用户登录。 运行以下命令更新系统软件包: yum update安装LibreOffice依赖项: yum install -y libreoffice-headless libreoffice-writer libreoffice-calc libreoffice-…...
Steam-V Rising 私人服务器架设教程
一、安装前的准备 一台服务器 拥有公网IP并且做好了端口映射 二、使用SteamCMD安装服务器 1.下载SteamCMD SteamCMD是Steam专用的命令行式客户端程序,所有的安装方式可以参照:https://developer.valvesoftware.com/wiki/SteamCMD 或者在其他站点自行…...
SpringBoot+Vue3实现登录验证码功能
系列文章目录 Redis缓存穿透、击穿、雪崩问题及解决方法Spring Cache的使用–快速上手篇分页查询–Java项目实战篇全局异常处理–Java实战项目篇 Java实现发送邮件(定时自动发送邮件)_java邮件通知_心态还需努力呀的博客-CSDN博客 该系列文章持续更新…...
spring2:创建和使用
目录 1.创建Spring项目 1.1创建Maven类 1.2添加Spring支持框架 1.3添加启动类 2.存储Bean对象 2.0 spring项目中添加配置文件(第一次) 2.1创建Bean 2.2把Bean注册到容器中 3.获取并使用Bean对象 3.1创建上下文 3.2获取指定Bean对象 getBean()方法 --> 获取什么…...
前端如何处理后端一次性传来的10w条数据?
写在前面 如果你在面试中被问到这个问题,你可以用下面的内容回答这个问题,如果你在工作中遇到这个问题,你应该先揍那个写 API 的人。 创建服务器 为了方便后续测试,我们可以使用node创建一个简单的服务器。 const http requir…...
Codeforces Round 867 (Div. 3)(A-G2)
文章目录 A. TubeTube Feed1、题目2、分析3、代码, B. Karina and Array1、题目2、分析3、代码 C. Bun Lover1、问题2、分析(1)观察样例法(2)正解推导 3、代码 D. Super-Permutation1、问题2、分析(1&#…...
蓝奥声核心技术分享——一种无线低功耗配置技术
1.技术背景 无线低功耗配置技术指基于对目标场景状态变化的协同感知而获得触发响应并进行智能决策,属于蓝奥声核心技术--边缘协同感知(EICS)技术的关键支撑性技术之一。该项技术涉及物联网边缘域的无线通信技术领域,具体主要涉及网络服务节点…...
kafka集群模拟单节点故障
这里通过kafka manage来展示节点宕机效果 现在三台主机节点均正常 topic正常识别到三个broker leader也均匀分配到了三个broker上 现在把节点id为0的主机模拟宕机 可以通过以上两张图片看到每个topic现在只识别到了两个broker节点,broker id为0的节点已经被剔除掉了 isr列…...
笔记:vue-cli-service
vue-cli-service serve 这个是什么意思? vue-cli-service serve 是一个 Vue.js CLI 命令,用于在本地开发环境下运行一个开发服务器,以便你可以在浏览器中查看和测试你的 Vue.js 应用程序。它在开发期间提供了自动重载、热模块替换和其它实用…...
Amazon S3 对象存储Java API操作记录(Minio与S3 SDK两种实现)
缘起 今年(2023年) 2月的时候做了个适配Amazon S3对象存储接口的需求,由于4月份自学考试临近,一直在备考就拖着没总结记录下,开发联调过程中也出现过一些奇葩的问题,最近人刚从考试缓过来顺手记录一下。 S3对象存储的基本概念 …...
ChatGPT技术原理 第六章:对话生成技术
目录 6.1 任务定义 6.2 基于检索的方法 6.3 基于生成的方法 6.4 评价指标 6.1 任务定义 对话生成技术是指使用自然语言处理技术生成与人类语言相似的对话。在对话生成任务中,模型需要理解输入的语境、用户的意图和上下文信息,然后生成能够回答用户问题…...
【C++ 八】写文件、读文件
写文件、读文件 文章目录 写文件、读文件前言1 文本文件1.1 写文件1.2 读文件 2 二进制文件2.1 写文件2.2 读文件 前言 本文包含文本文件写文件、文本文件读文件、二进制写文件、二进制读文件。 程序运行时产生的数据都属于临时数据,程序一旦运行结束都会被释放 通…...
【学习笔记】CF613E Puzzle Lover
这题本质上还是数据结构。 首先看到这个 2 n 2\times n 2n的网格图就很容易想到分治。我们还是考虑把要统计的东西变得可视化,一条路径要么穿过中线一次,那么我们可以将两边的串拼起来得到答案;要么穿过中线两次,考虑其中一边的…...
软考报名资格审核要多久?证明材料要哪些?
软考报名资格审核要多久? 一般来说,软考资格审核时间不超过1个工作日。当然,每个地区的具体情况都不一样。有些地区估计需要1-3个工作日。总之,为了顺利成功报名,大家应尽快报名,不要拖到最后一天。 软考…...
2023-04-27 polardbx-LSM-tree的Parallel Recovery性能优化
背景 数据库的Crash Recovery时长关系到数据库的可用性SLA、故障止损时间、升级效率等多个方面。本文描述了针对X-Engine数据库存储引擎的一种Crash Recovery优化手段,在典型场景下可以显著缩短数据库实例的故障恢复时间,提升用户使用感受。 当前面临的问题 X-Engine是阿里…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
