[蓝桥杯 2018 省 A] 付账问题 贪心题
几个人一起出去吃饭是常有的事。
但在结帐的时候,常常会出现一些争执。
现在有 n 个人出去吃饭,他们总共消费了 S 元。
其中第 i 个人带了 ai 元。
幸运的是,所有人带的钱的总数是足够付账的,但现在问题来了:每个人分别要出多少钱呢?
为了公平起见,我们希望在总付钱量恰好为 S 的前提下,最后每个人付的钱的标准差最小。
这里我们约定,每个人支付的钱数可以是任意非负实数,即可以不是 1分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍:标准差是多个数与它们平均数差值的平方平均数,一般用于刻画这些数之间的“偏差有多大”。
形式化地说,设第 i个人付的钱为 bi 元,那么标准差为 :

输入格式
第一行包含两个整数 n、S;
第二行包含 n个非负整数 a1, …, an。
输出格式
输出最小的标准差,四舍五入保留 4 位小数。
数据范围
1≤n≤5×105
0≤ai≤109
0≤S≤1015
输入样例1:
5 2333
666 666 666 666 666输出样例1:
0.0000输入样例2:
10 30
2 1 4 7 4 8 3 6 4 7输出样例2:
0.7928难度:中等 |
时/空限制:1s / 64MB |
来源:第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组 |
算法标签 贪心 |
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 500010;
long long int n, a[N];
int main()
{double s;cin >> n >> s;for (int i = 0; i < n; i++) scanf("%lld", &a[i]);sort(a, a + n);double res = 0, avg = s / n;for (int i = 0; i < n; i++){double cur = s / (n - i);if (a[i] < cur) cur = a[i];res += (cur - avg) * (cur - avg);s -= cur;}printf("%.4lf\n", sqrt(res/n));return 0;
}
相关文章:
[蓝桥杯 2018 省 A] 付账问题 贪心题
几个人一起出去吃饭是常有的事。但在结帐的时候,常常会出现一些争执。现在有 n 个人出去吃饭,他们总共消费了 S 元。其中第 i 个人带了 ai 元。幸运的是,所有人带的钱的总数是足够付账的,但现在问题来了:每个人分别要出…...
微机原理复习(周五),计算机组成原理图
1.计算机由运算器,控制器,存储器,输入设备,输出设备等5大基本部件组成。 2.冯诺依曼提出存储设计思想是:数字计算机的数制采用二进制,存储程序,程序控制。 3.计算机的基本组成框图:…...
用了10年Postman,意想不到它的Mock功能也如此强大
最近在做一些app,前后端分离的开发模式是必须的。一直用的python flask做后端的快速POC,python本身就是一门胶水语言,开发起来方便快捷,而flask又是一个极简的webserver框架(比Django简洁)。但在这里推荐的…...
项目重构,从零开始搭建一套新的后台管理系统
背景 应公司发展需求,我决定重构公司的后台管理系统,从提出需求建议到现在的实施,期间花了将近半个月的时间,决定把这些都记录下来。 之前的后台管理系统实在是为了实现功能而实现的,没有考虑到后期的扩展性…...
day20_Map
今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客_CSDN博客-Java2301 零、 复习昨日 一、作业 二、比较器排序 三、Collections 四、Map 五、HashMap 六、TreeMap 零、 复习昨日 HashSet 不允许重复元素,无序 HashSet去重原理: 先比较hashco…...
localStorage和sessionStorage
目录 一、localStorage和SessionStorage在哪里,是什么 二、localStorage和sessionStorage区别 三、localStorage常用方法 四、sessionStorage常用方法 一、localStorage和SessionStorage在哪里,是什么 【1】在浏览器开发者工具的Application栏目里&…...
IP地址,子网掩码,网段 概念详解
文章目录1. 子网掩码1.1 子网掩码的概念及作用1.2 子网掩码的组成1.3 子网掩码的表示方法1.4 为什么要使用子网掩码?1.5 子网掩码的分类2. 子网掩码和IP地址的关系2.1 根据掩码确定网段IP地址是以 网络号和 主机号来标示网络上的主机的,我们把网络号相同…...
数影周报:动视暴雪疑似数据泄露,数据出境安全评估申报最新进展
本周看点:动视暴雪疑似员工敏感信息及游戏数据泄露;谷歌云计算部门:两名员工合用一个工位;数据出境安全评估申报最新进展;TikTok Shop东南亚商城在泰国和菲律宾公布;智己汽车获九大金融机构50亿元贷款签约.…...
Web安全最详细学习路线指南,从入门到入职(含书籍、工具包)
在这个圈子技术门类中,工作岗位主要有以下三个方向: 安全研发 安全研究:二进制方向 安全研究:网络渗透方向 下面逐一说明一下. 第一个方向:安全研发 你可以把网络安全理解成电商行业、教育行业等其他行业一样&#x…...
ChatGPT?听说Biying把它下架了
ChatGPT被玩疯了,开始放飞自我 ChatGPT版微软必应上线不到10天…就被网友玩坏了 先说这个词,放飞自我,什么东西才会放飞自我? 人放飞自我,人?你确定是人? 所以让我们来把上面的句子改写一下。…...
中电金信:金融数字化转型路在何方?这里有答案
近期,媒体大数网整合了业内10份研究报告,详解金融数字化转型的思路、方法与路径。其中「中国电子金融级数字底座“源启”白皮书」也被收录其中。让我们一同阅读文章,探究金融数字化转型相关问题的答案吧。 当前,金融科技正在回归…...
【Leedcode】数据结构中链表必备的面试题(第五期)
【Leedcode】数据结构中链表必备的面试题(第五期) 文章目录【Leedcode】数据结构中链表必备的面试题(第五期)1.题目2.思路图解(1)第一步:复制每一个结点,插入到原结点和下一个结点之…...
ECDH secp256k1 集成
在Android 原生api是不支持secp256k1算法的,所以要先集成以下库:implementation com.madgag.spongycastle:core:1.58.0.0compile com.madgag.spongycastle:prov:1.54.0.0compile com.madgag.spongycastle:pkix:1.54.0.0compile com.madgag.spongycastle:…...
工单模型的理解与应用
工单(任务单)模型的定义 工单模型是一种分派任务的方法,可以用来跟踪、评估和报告任务的完成情况。它通常用于针对特定目标的重复性任务或项目,以确保任务能够按时完成并符合期望的标准。 工单模型的基本流程为:提…...
Python年利率计算器【N日年化收益率】
现在有闲钱的人,按照聪明等级从低到高排序应该是钱买股票,一年利率约为-20%钱放银行活期,年利率约为0.3%钱放银行定期,一年利率约为1.5%钱放余额宝(支付宝)或零钱通(微信)࿰…...
3年测试拿8K,被校招来的实习生反超薪资,其实你在假装努力
最近朋友给我分享了一个他公司发生的事 大概的内容呢:公司一位工作3年的测试工资还没有新人高,对此怨气不小,她来公司辛辛苦苦三年,三年内迟到次数都不超过5次,每天都是按时上下班,工作也按量完成…...
因子分析计算权重
因子分析两类权重计算方法总结 案例背景 疫情爆发以来,越来越多的人为了避免线下与人接触,选择了线上购买生活必需品。网购虽然方便快捷,但是随着订单压力的增加,物流问题也随之出现,近期有很多卖家收到物流投诉的问题…...
国家调控油价预测案例+源码
项目git地址:https://github.com/Boris-2021/Oil-price-control-forecast 使用已知的历史数据:日期、汇率、布伦特、WTI、阿曼原油价格,预测下一个调价周期中的汽油、柴油零售限价的调价价格。 一. 需求 1.1 需求说明 使用已知的历史数据&a…...
Gephi快速入门
Gephi快速入门1. 导入文件(Import file)2. 布局(Layout)3. 排序(Ranking)4. 指标(Metrics)5. 标签(Label)6. 社区发现(Community detection&#…...
GitHub
什么是 Github?GitHub是一个面向开源及私有软件项目的托管平台,因为只支持Git作为唯一的版本库格式进行托管,故名GitHub。一、常用词Watch:观察。如果watch了一个项目,之后这个项目有更新,你会在第一时间收到该项目更…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
