[蓝桥杯 2018 省 A] 付账问题
【蓝桥杯】付账问题
[蓝桥杯 2018 省 A] 付账问题
题目描述
几个人一起出去吃饭是常有的事。但在结帐的时候,常常会出现一些争执。
现在有 n n n 个人出去吃饭,他们总共消费了 S S S 元。其中第 i i i 个人带了 a i a_i ai 元。幸运的是,所有人带的钱的总数是足够付账的,但现在问题来了:每个人分别要出多少钱呢?
为了公平起见,我们希望在总付钱量恰好为 S S S 的前提下,最后每个人付的钱的标准差最小。这里我们约定,每个人支付的钱数可以是任意非负实数,即可以不是 1 1 1 分钱的整数倍。你需要输出最小的标准差是多少。
标准差的介绍:标准差是多个数与它们平均数差值的平方平均数,一般用于刻画这些数之间的“偏差有多大”。形式化地说,设第 i i i 个人付的钱为 b i b_i bi 元,那么标准差为 s = 1 n ∑ i = 1 n ( b i − 1 n ∑ i = 1 n b i ) s=\sqrt{\frac{1}{n}\sum_{i=1}^n(b_i-\frac{1}{n}\sum_{i=1}^n b_i)} s=n1∑i=1n(bi−n1∑i=1nbi)
输入格式
第一行包含两个整数 n n n、 S S S;
第二行包含 n n n 个非负整数 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an。
输出格式
输出到标准输出。
输出最小的标准差,四舍五入保留 4 4 4 位小数。
保证正确答案在加上或减去 1 0 − 9 10^{-9} 10−9 后不会导致四舍五入的结果发生变化。
样例 #1
样例输入 #1
5 2333
666 666 666 666 666
样例输出 #1
0.0000
样例 #2
样例输入 #2
10 30
2 1 4 7 4 8 3 6 4 7
样例输出 #2
0.7928
提示
【样例解释】
- 每个人都出 2333/5 元,标准差为 0。
【数据约定】
对于 10 % 10\% 10% 的数据,所有 a i a_i ai 相等;
对于 30 % 30\% 30% 的数据,所有非 0 0 0 的 a i a_i ai 相等;
对于 60 % 60\% 60% 的数据, n ≤ 1000 n \le 1000 n≤1000;
对于 80 % 80\% 80% 的数据, n ≤ 1 0 5 n \le 10^5 n≤105;
对于所有数据, n ≤ 5 × 1 0 5 , 0 ≤ a i ≤ 1 0 9 n \le 5 \times 10^5,0 \le a_i \le 10^9 n≤5×105,0≤ai≤109。
标签:贪心
思路:
标准差,即数据的分散程度,分散度高标准差大,反之则越小。
我们使标准差小,则尽可能让数据集中在平均数附近
$ a_i<avg(平均数) , 则 ,则 ,则b_i=a_i$ a v g − a i avg-a_i avg−ai为不够的钱,由钱多的均摊
有5个人带的钱为 a 1 , a 2 , a 3 , a 4 , a 5 a_1,a_2,a_3,a_4,a_5 a1,a2,a3,a4,a5,avg为每个人付款的平均数,总付款sum
a 1 a1 a1小于 a v g avg avg,因此他只能付 a 1 a1 a1,多的钱 a v g − a 1 avg-a1 avg−a1由 a 2 到 a 5 a_2到a_5 a2到a5来均摊,
即付款c = s u m − a 1 / ( n − 1 ) =sum-a1/(n-1) =sum−a1/(n−1),如果 c > a 2 c>a2 c>a2,同样 a 2 a2 a2拿出所有的钱,剩下的由后面的均摊,以此类推
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
long double money[N];
signed main()
{int n; long double s=0.0;//注意这里,虽然将int定义为long long但输入的是long long 类型时,输入格式一定还是%lld,否则会出错scanf("%lld %Lf",&n,&s);//long double输入输出格式为%Lflong double ave=s/n;//平均数for(int i=0;i<n;i++)scanf("%Lf",&money[i]);sort(money,money+n);long double sum=0,t=0;for(int i=0;i<n;i++)//想让我们的标准差小,每个数尽量集中在平均数附近,先排序,遍历一遍这些数//如果这个数小于平均数,就要拿出全部的值,不够的钱a由钱多于平均数的人去均摊,使后面的人的付钱平均数提高//可能出现因为平均数提高后面的人也拿不出来这么多钱,那我们就让他拿出全部钱,剩下的钱仍由更后面的人去分摊{t=min(s/(n-i),money[i]);//注意min里的参数中数据类型要一致,即int对应int,long double和long double对应sum+=(t-ave)*(t-ave);s-=t;}printf("%.4Lf",sqrt(sum/n));return 0;
}
相关文章:
[蓝桥杯 2018 省 A] 付账问题
【蓝桥杯】付账问题 [蓝桥杯 2018 省 A] 付账问题 题目描述 几个人一起出去吃饭是常有的事。但在结帐的时候,常常会出现一些争执。 现在有 n n n 个人出去吃饭,他们总共消费了 S S S 元。其中第 i i i 个人带了 a i a_i ai 元。幸运的是&#…...
设计模式|装饰器模式(Decorator Pattern)
文章目录 结构优缺点优点缺点适用场景示例装饰器模式(Decorator Pattern)是一种结构型设计模式,它允许在不改变原始对象的基础上,动态地给对象添加新的功能或责任。这种模式是通过创建一个包装对象,也就是装饰器,来包裹真实的对象,然后在装饰器中添加新的行为或功能。这…...
发作性睡病有性别差异吗?
发作性睡病是一种特殊的睡眠障碍,以不可控制的嗜睡、猝倒发作、睡眠瘫痪、入睡前幻觉以及夜间睡眠紊乱为主要临床特点。关于发作性睡病是否存在性别差异,不同的研究和报道给出了不同的结论。 一方面,从生理角度来看,男性和女性在…...
ppt从零基础到高手【办公】
第一章:文字排版篇01演示文稿内容基密02文字操作规范03文字排版处理04复习&作业解析第二章:图形图片图表篇05图形化表达06图片艺术化07轻松玩转图表08高效工具&母版统一管理09复习&作业解析10轻松一刻-文字图形小技巧速学第三章:…...
文件上传下载
文章目录 文件上传下载文件上传文件下载 文件上传下载 HTTP请求会包含一个请求头,其中"Content-Type"字段告诉服务器正在发送什么类型的数据。根据发送的数据类型,浏览器和服务器会采取适应的处理方式。 "multipart/form-data"是一…...
C++11 新特性:新增算法
C11 在标准库中引入了一系列新的算法,这些新增的算法使我们的代码写起来更简洁方便。 下面是 C11 中新增加的一些重要算法的简要描述和使用方法: 1、非修改序列操作 std::all_of:检查范围内的所有元素是否都满足指定的谓词。std::any_of&a…...
c/c++普通for循环学习
学习一下 for 循环的几种不同方式,了解一下原理及差异 完整的测试代码参考 GitHub :for 循环测试代码 1 常用形态 对于 for 循环来说,最常用的形态如下 for (表达式1; 表达式2; 表达式3) {// code }流程图如下: 编写测试代码…...
操作系统组成部分
从1946年诞生第一台电子计算机。 冯诺依曼结构 冯诺依曼是:数字计算机的数制采用二进制;计算机应该按照程序顺序执行。 常见的操作系统有三种类型 单用户单任务操作系统:只支持一个用户和一个任务的执行,如DOS;单用…...
深入理解DES算法:原理、实现与应用
title: 深入理解DES算法:原理、实现与应用 date: 2024/4/14 21:30:21 updated: 2024/4/14 21:30:21 tags: DES加密对称加密分组密码密钥管理S盒P盒安全性分析替代算法 DES算法简介 历史 DES(Data Encryption Standard)算法是由IBM研发&…...
# 达梦sql查询 Sql 优化
达梦sql查询 Sql 优化 文章目录 达梦sql查询 Sql 优化注意点测试数据单表查询 Sort 语句优化优化过程 多表关联SORT 优化函数索引的使用 注意点 关于优化过程中工具的选用,推荐使用自带的DM Manage,其它工具在查看执行计划等时候不明确在执行计划中命中…...
Linux下SPI驱动:SPI设备驱动简介
一. 简介 Linux下的SPI 驱动框架和 I2C 很类似,都分为主机控制器驱动和设备驱动,主机控制器也就是 SOC的 SPI 控制器接口,SPI设备驱动也就是所操作的SPI设备的驱动。 本文来学习一下Linux下SPI设备驱动。 二. Linux下SPI驱动:SP…...
【简明图文教程】Node.js的下载、安装、环境配置及测试
文章目录 前言下载Node.js安装Node.js配置Node.js配置环境变量测试后言 前言 本教程适用于小白第一次从零开始进行Node.js的下载、安装、环境配置及测试。 如果你之前已经安装过了Node.js或删除掉了Node.js想重新安装,需要先参考以下博客进行处理后,再根…...
共模电感饱和与哪些参数有关?这些参数是如何影响共模电感的?
在做一个变频器项目,遇到一个问题,在30Hz重载超过一定1小时,CE测试结果超出限制,查找原因最终发现EMI filter内的共模电感加热,fail现象可以复现。最终增大Y电容把问题解决了。由此问题引申出一个问题,到底…...
儿童护眼台灯怎么选?五款必选的高口碑护眼台灯推荐
儿童台灯,想必大家都不会陌生了,是一种学生频繁使用的小灯具,一般指放在桌面用的有底座的电灯。随着近年来儿童青少年的视力急速下滑,很多家长都会选择给孩子选择一款合适的护眼台灯,以便孩子夜晚学习能有个好的照明环…...
前端小技巧之轮播图
文章目录 功能htmlcssjavaScript图片 设置了一点小难度,不理解的话,是不能套用的哦!!! (下方的圆圈与图片数量不统一,而且宽度是固定的) 下次写一些直接套用的,不整这些麻…...
手动实现简易版RPC(上)
手动实现简易版RPC(上) 前言 什么是RPC?它的原理是什么?它有什么特点?如果让你实现一个RPC框架,你会如何是实现?带着这些问题,开始今天的学习。 本文主要介绍RPC概述以及一些关于RPC的知识,为…...
大语言模型总结整理(不定期更新)
《【快捷部署】016_Ollama(CPU only版)》 介绍了如何一键快捷部署Ollama,今天就来看一下受欢迎的模型。 模型简介gemmaGemma是由谷歌及其DeepMind团队开发的一个新的开放模型。参数:2B(1.6GB)、7Bÿ…...
关于npm和yarn的使用(自己的问题记录)
目录 一 npm 和 yarn 的区别 二 npm 和 yarn 常用命令对比 1. 初始化项目 2. 安装所有依赖包 3. 安装某个依赖包 4.安装某个版本的依赖包 5. 更新依赖包 5. 移除依赖包 三 package.json中 devDependencies 和 dependencies 的区别。 四 npm安装包时,…...
Web端Excel的导入导出Demo
📚目录 📚简介:✨代码的构建:💭Web端接口Excel操作🚀下载接口🚀导入读取数据接口 🏡本地Excel文件操作⚡导出数据🌈导入读取数据 📚简介: 使用阿里巴巴开源组件Easy Exce…...
Java日期正则表达式(附Demo)
目录 前言1. 基本知识2. Demo 前言 对于正则匹配,在项目实战中运用比较广泛 原先写过一版Python相关的:ip和端口号的正则表达式 1. 基本知识 对于日期的正则相对比较简单 以下是一些常见的日期格式及其对应的正则表达式示例: 年-月-日&a…...
基于LabVIEW的CAN通信系统开发案例
基于LabVIEW的CAN通信系统开发案例 介绍了基于LabVIEW开发的CAN通信系统,该系统主要用于汽车行业的数据监控与分析。通过对CAN通信协议的有效应用,实现了车辆控制系统的高效信息交换与实时数据处理,从而提升了车辆性能的检测与优化能力。 项…...
SAP SD学习笔记07 - 紧急发注(急单),现金贩卖,贩卖传票Type/ 明细Category 及其Customize
上面讲SAP中主干流程的时候,还有后面讲一括处理的时候,都用的是 OR 标准受注。 SAP SD学习笔记01 - 简单走一遍SD的流程:受注,出荷,请求_怎么学好sd模块-CSDN博客 下面开始讲一些稀奇古怪的非标准流程。 当然&#x…...
(六)C++自制植物大战僵尸游戏关卡数据讲解
植物大战僵尸游戏开发教程专栏地址http://t.csdnimg.cn/xjvbb 游戏关卡数据文件定义了游戏中每一个关卡的数据,包括游戏类型、关卡通关奖励的金币数量、僵尸出现的波数、每一波出现僵尸数量、每一波僵尸出现的类型等。根据不同的游戏类型,定义了不同的通…...
Java基于微信小程序的校园外卖平台设计与实现,附源码
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
渗透工具及其知识库(个人笔记)
1.IP搜寻 查看kali网段: ip addr 、 ifconfig namp:nmap -sP xxx.xxx.xxx.0/24 netdiscover:netdiscover xxx.xxx.xxx.0/24 arp:arp-scan -l 2.端口扫描 粗略扫描:nmap <IP> 深度扫描: …...
MongoDB的使用
一、Spring Boot集成MongoDB 1 引用依赖包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-mongodb</artifactId></dependency> 2 配置文件配置mongodb资料 # MongoDB连接信息 spring.…...
labview中FP.isFrontmost不生效?
主GUI界面中调用子GUI程序FP.isFrontmost不生效? 如果主GUI程序使用“floating”,子GUI程序使用default动作,则子GUI无法打开到最前。子GUI程序只能使用“模态”才能置顶。 主GUI程序: 子GUI程序: 改正的方法很简单,…...
Vela-OS: 记录一个class层,处理MSC协议的bug
一、关于USC-MSC类设备驱动层,处理SCSI指令的代码逻辑问题 1. 源文件 \nuttx\drivers\usbdev\usbmsc_scsi.c 2. 问题描述 对于INQUIRY指令,长度一般是6个字节,cdblen字段嵌入在CBW数据包中,如下: 命令阶段的CBW数据包: 55 53 42 43 60 2a c0 8b 24 00 00 00 0x80 0x…...
跨框架探索:React Redux 和 Vuex 对比分析快速掌握React Redux
React Redux 和 Vuex 都是前端状态管理库,分别用于 React 和 Vue.js 框架。 它们都提供了一套规范的状态管理机制,帮助开发者更好地组织和管理应用状态。下面是它们的一些异同点: 相同点: 中心化状态管理:两者都提…...
第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结
目录 个人总结 C/C 组真题 握手问题 小球反弹 好数 R 格式 宝石组合 数字接龙 爬山 拔河 编辑 再总结及后续规划 个人总结 第一次参加蓝桥杯,大二,以前都在在学技术,没有系统的学过算法。所以,还是花了挺多时间去备…...
网站建设的违约责任怎么写/seo的基本工作内容
1.问题 ubuntu18.04自带了python2.7,工作需要安装了其他版本的python(anaconda,python3.5)。使用中,遇到输入python ****.py时可以正常运行,但是sudo python ***.py时出现包导入错误:ImportErr…...
苏州长尾词seo排名优化/信息如何优化上百度首页
来到2012年已经好多天了,老早就想着写一篇文字,来记录一下2011年,去年想写但没写出来,现在回头去想已经忘记很多事了,今年还是写一下吧,万一真的2012了呢。 我是很物质的人,先记录一下今年购入的…...
WordPress进/兰州网站seo诊断
DevExpress广泛应用于ECM企业内容管理、 成本管控、进程监督、生产调度,在企业/政务信息化管理中占据一席重要之地。通过DevExpress WPF Controls,您能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的需求和构建未来新…...
毕业设计代做网站价格/深圳关键词排名seo
今日执行项目更新时,手贱点击了cancel 中断了操作,最后导致项目被锁,杯具了。 首先想到了Clean up 直接提示 看来不行呀 …// 省略 n 多种尝试 最后使用删除db 中的 lock 表来解决了这个问题 首先cd 到项目下然后执行如下操作 c:\> sqlite3 .svn/…...
花店网站建设毕设介绍/电子商务平台
2009年,华晨汽车在德国的Euro NCAP标准碰撞测试中成绩糟糕,成为当年中国汽车业的典型事件。“碰撞门”后的沈阳华晨金杯汽车正视问题,对自主品牌遇到这种挫折,抑或是一种壁垒,但公司承认与和世界发达国家的一些企业有很…...
怎么查看网站用什么做的/aso优化师
自动驾驶到底怎么了? 进入2021年,在驾驶辅助技术方面,随着算法的继续迭代、算力的持续提升、更多传感器的加入,在驾驶员保持时刻监管的情况下,无论是功能升级还是场景的突破,都已经取得了很大进展…...