[蓝桥杯 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了一个项目,之后这个项目有更新,你会在第一时间收到该项目更…...
3大优化方案让经典游戏重获新生:WarcraftHelper解决老游戏新设备适配难题
3大优化方案让经典游戏重获新生:WarcraftHelper解决老游戏新设备适配难题 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 当你在4K显示器上…...
Qwen3.5-9B-AWQ-4bit多模态落地:制造业设备铭牌识别→型号查询→维保文档匹配
Qwen3.5-9B-AWQ-4bit多模态落地:制造业设备铭牌识别→型号查询→维保文档匹配 1. 制造业设备管理的痛点与解决方案 在制造业设备管理中,设备铭牌识别、型号查询和维保文档匹配是三个关键但繁琐的环节。传统方式需要人工拍照、记录铭牌信息,…...
基于CasRel的微信小程序开发:智能合同关键信息抽取工具
基于CasRel的微信小程序开发:智能合同关键信息抽取工具 1. 引言 你有没有过这样的经历?面对一份几十页的合同,需要手动找出甲方、乙方、合同金额、签约日期、违约责任条款……一页页翻,一行行看,不仅耗时费力&#x…...
Git Diff View:三分钟学会实用的代码差异对比组件
Git Diff View:三分钟学会实用的代码差异对比组件 【免费下载链接】git-diff-view A Diff View component for React / Vue, just like Github 项目地址: https://gitcode.com/gh_mirrors/gi/git-diff-view 你是否曾经在代码审查中为理解复杂的Git差异而头疼…...
如何编写全面的golang-lru单元测试:覆盖所有边界条件的完整指南
如何编写全面的golang-lru单元测试:覆盖所有边界条件的完整指南 【免费下载链接】golang-lru Golang LRU cache 项目地址: https://gitcode.com/gh_mirrors/go/golang-lru 在Go语言开发中,缓存是提升性能的关键组件,而golang-lru作为一…...
音频处理避坑指南:二进制编码转换中的常见问题与解决方案
音频处理避坑指南:二进制编码转换中的常见问题与解决方案 音频处理在现代多媒体应用中扮演着重要角色,从语音识别到音乐制作,从流媒体传输到嵌入式设备音频播放,二进制编码转换都是核心技术环节。对于有一定经验的开发者而言&…...
突破网盘限制的高效工具:解锁全速下载与无缝分享的实战指南
突破网盘限制的高效工具:解锁全速下载与无缝分享的实战指南 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 ,支持 百度网盘 / 阿里云盘 / 中国移动云盘 /…...
收藏!小白程序员必看:Agent和工作流是最佳拍档,教你如何协同它们(附案例)
文章探讨了AI智能体(Agent)和工作流工具的关系,指出它们并非竞争对手,而是最佳拍档。Agent擅长自主决策和动态规划,适用于探索性和不确定性任务;工作流则负责流程编排和确定性执行,适用于重复性…...
让老旧Mac焕发新生:OpenCore Legacy Patcher完整指南
让老旧Mac焕发新生:OpenCore Legacy Patcher完整指南 【免费下载链接】OpenCore-Legacy-Patcher Experience macOS just like before 项目地址: https://gitcode.com/GitHub_Trending/op/OpenCore-Legacy-Patcher 您的Mac是否被苹果官方"抛弃"&…...
如何通过InstantClick事件回调实现精准的性能监控:开发者必备指南
如何通过InstantClick事件回调实现精准的性能监控:开发者必备指南 【免费下载链接】instantclick InstantClick makes following links in your website instant. 项目地址: https://gitcode.com/gh_mirrors/in/instantclick InstantClick是一款能让网站链接…...
