贪心算法练习day1
练习1--翻硬币
1)题目及要求
2)解题思路
输入的是字符串,要想将两组字符串进行一一对比,需要将字符串转换成字符数组,再使用for循环依次遍历字符数组,进行比对。
输入两行字符串,转换成两个字符数组;将初始数组和目标数组进行逐个对比,运用三目运算符进行判断
3)详细代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...String origin=scan.next();String target=scan.next();char[] originLine=origin.toCharArray();char[] targetLine=target.toCharArray();int result=0;for(int i=0;i<originLine.length-1;i++){if(originLine[i]!=targetLine[i]){originLine[i]=originLine[i]== '*'?'o':'*';originLine[i+1]=originLine[i+1]== '*'?'o':'*';result++;}}scan.close();System.out.println(result);}
}
4)本题核心
if(originLine[i]!=targetLine[i]){originLine[i]=originLine[i]== '*'?'o':'*';originLine[i+1]=originLine[i+1]== '*'?'o':'*';result++;}
练习2--付账
1)题目及要求
2)解题思路
让每个人尽可能付接近平均金额的钱数
根据金额和人数计算平均金额;对每个人的钱数进行从小到大排序;遍历排序后,将钱数少于平均金额的人 全部支付,再从总金额里减去该人所支付的金额;重新计算平均金额,剩余金额/剩余人数,同样钱数少于新平均金额的人也全部支付;最后钱最多的人支付剩余的。以此类推
3)详细代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;/*** 贪心:为了使得标准差最小,每一个出的钱bi必须接近平均值s/n* [1]第i个人带的钱不够平均数avg,那么他只能出自己全部的钱ai* [2]第i个人带的钱比平均数avg多,那么他可以多付一些。** 基本步骤如下:* 1、对ai从小到大排序* 2、排序后前一部分人的钱不够,那么就出他们所有的钱* 3、从总付钱数中扣除前一部分人出的钱,得剩余需要出得钱数为S',* 以及剩余得后一部分人的出钱平均数avg'* 4、后一部分人的钱多,他们多出一些:* (1)比较有钱的,但是他的钱也不够avg',那么他的钱也是全部出* (2)非常有钱的,不管怎么付他都有富余*/
public class Main {public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public static void main(String[] args) throws IOException {int n = nextInt();long s = nextLong();long[] a = new long[n];//每个人带的钱数for (int i = 0; i <n ; i++) {a[i]=nextLong();}//开始贪心选择Arrays.sort(a);//排序,从小到大double avg=1.0*s/n;double sum=0;for (int i = 0; i <n; i++) {if(a[i]*(n-i)<s){ //把钱全部拿出的人sum+=(a[i]-avg)*(a[i]-avg);s-=a[i]; //更新还差多少钱}else{ //不需要把钱全部拿出的人。剩下的人中,钱最少的人都可以达到cur_avgdouble cur_avg=1.0*s/(n-i);//注意这里的s是还差多少钱//如果这个人有钱付,那么后面的人一定也能付,所以直接乘后面的人数(n - i)即可sum+=(cur_avg-avg)*(cur_avg-avg)*(n-i);break;}}System.out.printf("%.4f",Math.sqrt(sum/n));}public static int nextInt() throws IOException{st.nextToken();return (int)st.nval;}public static long nextLong() throws IOException{st.nextToken();return (long)st.nval;}
}
4)本题核心
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Scanner scanner = new Scanner(br); int n = scanner.nextInt(); long s = scanner.nextLong(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextLong(); } // ... (其余代码逻辑保持不变) }
}
-
输入和初始化:
- 通过
StreamTokenizer
和BufferedReader
从标准输入读取数据。 nextInt()
和nextLong()
方法用于读取整数和长整数。- 初始化变量
n
(人数)、s
(总金额需求)和a
数组(每个人持有的钱)。
- 通过
-
排序:
- 使用
Arrays.sort(a)
对a
数组进行排序,以确保从小到大的顺序。这是贪心策略的一部分,因为我们希望先使用钱较少的人来尽量接近平均值。
- 使用
-
计算平均值:
- 计算总需求
s
的平均值avg
。
- 计算总需求
-
贪心选择:
- 遍历排序后的
a
数组。对于每个人,我们检查他们是否有足够的钱来支付平均值。- 如果某人的钱不足以支付平均值(即
a[i] * (n - i) < s
),那么他们会把所有的钱都拿出来。此时,我们更新总需求s
,并计算这个人与平均值的差的平方,累加到sum
中。 - 如果某人的钱足够支付平均值,那么他们会支付平均值的金额,而后面的所有人也都能至少支付这个金额。因此,我们计算当前平均值与总平均值的差的平方,并乘以剩余的人数
(n - i)
,然后累加到sum
中。之后,我们跳出循环,因为没有必要再检查后面的人。
- 如果某人的钱不足以支付平均值(即
- 遍历排序后的
-
计算标准差:
- 使用公式
Math.sqrt(sum / n)
计算标准差,并保留四位小数后输出。这里,sum
是每个人与平均值的差的平方的总和,而n
是人数。标准差是衡量这组数分布离散程度的指标。
- 使用公式
相关文章:
贪心算法练习day1
练习1--翻硬币 1)题目及要求 2)解题思路 输入的是字符串,要想将两组字符串进行一一对比,需要将字符串转换成字符数组,再使用for循环依次遍历字符数组,进行比对。 输入两行字符串,转换成两个字…...
[VulnHub靶机渗透] WestWild 1.1
🍬 博主介绍👨🎓 博主介绍:大家好,我是 hacker-routing ,很高兴认识大家~ ✨主攻领域:【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 🎉点赞➕评论➕收藏…...
如何使用 ControlValueAccessor 在 Angular 中创建自定义表单控件
简介 在 Angular 中创建表单时,有时您希望拥有一个不是标准文本输入、选择或复选框的输入。通过实现 ControlValueAccessor 接口并将组件注册为 NG_VALUE_ACCESSOR,您可以将自定义表单控件无缝地集成到模板驱动或响应式表单中,就像它是一个原…...
视频讲解:优化柱状图
你好,我是郭震 AI数据可视化 第三集:美化柱状图,完整视频如下所示: 美化后效果前后对比,前: 后: 附完整案例源码: util.py文件 import platformdef get_os():os_name platform.syst…...
OpenAI宣布ChatGPT新增记忆功能;谷歌AI助理Gemini应用登陆多地区
🦉 AI新闻 🚀 OpenAI宣布ChatGPT新增记忆功能,可以自由控制内存,提供个性化聊天和长期追踪服务 摘要:ChatGPT新增的记忆功能可以帮助AI模型记住用户的提问内容,并且可以自由控制其内存。这意味着用户不必…...
Solidworks:平面草图练习
继续练习平面草图,感觉基本入门了。...
React18原理: 渲染与更新时的重点关注事项
概述 react 在渲染过程中要做很多事情,所以不可能直接通过初始元素直接渲染还需要一个东西,就是虚拟节点,暂不涉及React Fiber的概念,将vDom树和Fiber 树统称为虚拟节点有了初始元素后,React 就会根据初始元素和其他可…...
嵌入式I2C 信号线为何加上拉电阻(图文并茂)
IIC 是一个两线串行通信总线,包含一个 SCL 信号和 SDA 信号,SCL 是时钟信号,从主设备发出,SDA 是数据信号,是一个双向的,设备发送数据和接收数据都是通过 SDA 信号。 在设计 IIC 信号电路的时候我们会在 SC…...
Vite 5.0 正式发布
11 月 16 日,Vite 5.0 正式发布,这是 Vite 道路上的又一个重要里程碑!Vite 现在使用 Rollup 4,这已经代表了构建性能的大幅提升。此外,还有一些新的选项可以改善开发服务器性能。 Vite 4 发布于近一年前,它…...
嵌入式STM32 单片机 GPIO 的工作原理详解
STM32的 GPIO 介绍 GPIO 是通用输入/输出端口的简称,是 STM32 可控制的引脚。GPIO 的引脚与外部硬件设备连接,可实现与外部通讯、控制外部硬件或者采集外部硬件数据的功能。 以 STM32F103ZET6 芯片为例子,该芯片共有 144 脚芯片,…...
系统调用的概念
在嵌入式开发、操作系统开发以及一般的系统编程中,系统调用是一个核心概念。它允许用户空间程序请求内核执行某些操作,如打开文件、读写数据、创建进程等。这些操作通常需要特殊的权限或访问硬件资源,因此不能直接在用户模式下执行。 系统调…...
【无标题】Matlab 之axes函数——创建笛卡尔坐标区
**基本用法:**axes 在当前图窗中创建默认的笛卡尔坐标区,并将其设置为当前坐标区。 应用场景1:在图窗中放置两个 Axes 对象,并为每个对象添加一个绘图。 要求1:指定第一个 Axes 对象的位置,使其左下角位于…...
2.12:C语言测试题
1.段错误:申请堆区内存未返回,str指向NULL 2.段错误:局部变量,本函数结束,p也释放 3.越界访问,可能正常输出hello,可能报错 4.可能段错误,释放后,str未指向NULL&#x…...
【Linux】yum软件包管理器
目录 Linux 软件包管理器 yum 什么是软件包 Linux安装软件 查看软件包 关于rzsz Linux卸载软件 查看yum源 扩展yum源下载 Linux开发工具 vim编辑器 上述vim三种模式之间的切换总结: 命令模式下,一些命令: vim配置 Linux 软件包管理…...
「优选算法刷题」:寻找旋转排序数组中的最小值
一、题目 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]若旋转 7 次…...
MySQL 基础入门指南:从安装到基本操作
一、简介 MySQL 是一种流行的开源关系型数据库管理系统,被广泛用于各种规模和类型的应用程序中。如果您对 MySQL 还不熟悉,本文将为您提供一个基础的入门指南,从安装到基本操作。 1.1 安装 MySQL 首先,您需要下载并安装 MySQL。…...
嵌入式Qt Qt Creator安装与工程介绍
一.Qt概述 什么是Qt:Qt是一个跨平台的C图形用户界面应用程序框架。它为应用程序开发者提供建立图形界面所需的所有功能。它是完全面向对象的,很容易扩展,并且允许真正的组件编程。 二.Qt Creator下载安装 下载地址:Index of /a…...
Windows 系统盘(C盘)爆红如何清理、如何增加C盘空间
1、简介 Windows系统中,系统和保留占用太多的空间,一旦系统盘分配空间较少,使用一段时间后,备份文件、临时文件、系统更新记录等都会在占用系统盘较大空间,导致系统盘空间不够使用,会造成应用运行卡顿。如何…...
【JavaEE Spring】Spring 原理
Spring 原理 1. Bean的作⽤域1.1 概念1.2 Bean的作⽤域 2. Bean的⽣命周期 1. Bean的作⽤域 1.1 概念 在Spring IoC&DI阶段, 我们学习了Spring是如何帮助我们管理对象的. 通过 Controller , Service , Repository , Component , Configuration ,Bean 来声明Bean对象。通…...
【Crypto | CTF】RSA打法
天命:我发现题题不一样,已知跟求知的需求都不一样 题目一:已知 p q E ,计算T,最后求D 已知两个质数p q 和 公钥E ,通过p和q计算出欧拉函数T,最后求私钥D 【密码学 | CTF】BUUCTF RSA-CSDN…...
红衣大叔讲AI:从OpenAI发布首个视频大模型Sora,谈2024年视觉大模型的十大趋势
OpenAI宣布推出全新的生成式人工智能模型“Sora”。据了解,通过文本指令,Sora可以直接输出长达60秒的视频,并且包含高度细致的背景、复杂的多角度镜头,以及富有情感的多个角色。 OpenAI发布首个视频大模型Sora,一句话生…...
java远程连接Linux执行命令的三种方式
java远程连接Linux执行命令的三种方式 1. 使用JDK自带的RunTime类和Process类实现2. ganymed-ssh2 实现3. jsch实现4. 完整代码:执行shell命令下载和上传文件 1. 使用JDK自带的RunTime类和Process类实现 public static void main(String[] args){Process proc Run…...
JavaScript- let var const区别
let 允许你声明⼀个作⽤域被限制在块级中的变量、语句或者表达式 let 绑定不受变量提升的约束,这意味着 let 声明不会被提升到当前 该变量处于从块开始到初始化处理的“暂存死区” function example() {let x 10;if (true) {let x 20;console.log(x); // Outpu…...
指针的经典笔试题
经典的指针试题,让你彻底理解指针 前言 之前对于指针做了一个详解,现在来看一些关于指针的经典面试题。 再次说一下数组名 数组名通常表示的都是首元素的地址,但是有两个意外,1.sizeof(数组名)这里数组名…...
书生浦语大模型实战营-课程笔记(1)
模型应用过程,大致还是了解的。和之前实习做CV项目的时候比起来,多了智能体这个环节。智能体是个啥? 类似上张图,智能体不太清楚。感觉是偏应用而不是模型的东西? 数据集类型很多,有文本/图片/视频。所以…...
磁盘database数据恢复: ddrescue,dd和Android 设备的数据拷贝
ddrescue和dd 区别: GNU ddrescue 不是 dd 的衍生物,也与 dd 没有任何关系 除了两者都可用于将数据从一台设备复制到另一台设备。 关键的区别在于 ddrescue 使用复杂的算法来复制 来自故障驱动器的数据,尽可能少地造成额外的损坏。ddrescue…...
SpringMVC-入门
1.概念 SpringMVC是一种软件架构思想,把软件按照模型(Model)、视图(View)、控制器(Controller)这三层来划分。Model:指的是工程中JavaBean,用来处理数据View:指的是工程中的html、jsp等页面,用来展示给用户数据Control…...
需要学习的知识点清单
div 4 div 3 F :拓扑排序 G : 组合数学 D : 结构体排序 div 2 div 12...
杂谈--spconv导出中onnx的扩展阅读
Onnx 使用 Onnx 介绍 Onnx (Open Neural Network Exchange) 的本质是一种 Protobuf 格式文件,通常看到的 .onnx 文件其实就是通过 Protobuf 序列化储存的文件。onnx-ml.proto 通过 protoc (Protobuf 提供的编译程序) 编译得到 onnx-ml.pb.h 和 onnx-ml.pb.cc 或 on…...
嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第二天-arm ads下的start.S分析(物联技术666)
链接:https://pan.baidu.com/s/1E4x2TX_9SYhxM9sWfnehMg?pwd1688 提取码:1688 ; ; NAME: 2440INIT.S ; DESC: C start up codes ; Configure memory, ISR ,stacks ; Initialize C-variables ; 完全注释 ; HISTORY: ; 2002.02.25:kwtark: ver 0.…...
STL之list容器的介绍与模拟实现+适配器
STL之list容器的介绍与模拟实现适配器 1. list的介绍2. list容器的使用2.1 list的定义2.2 list iterator的使用2.3 list capacity2.4 list element access2.5 list modifiers2.6 list的迭代器失效 3. list的模拟实现3.1 架构搭建3.2 迭代器3.2.1 正向迭代器3.2.2反向迭代器适配…...
Leetcode With Golang 二叉树 part1
这一部分主要来梳理二叉树题目最简单最基础的部分,包括遍历,一些简单题目。 一、Leecode 144 - 二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 二叉树的遍历是入门。我们需要在程序一开始就创建一个空…...
tcp 中使用的定时器
定时器的使用场景主要有两种。 (1)周期性任务 这是定时器最常用的一种场景,比如 tcp 中的 keepalive 定时器,起到 tcp 连接的两端保活的作用,周期性发送数据包,如果对端回复报文,说明对端还活着…...
黑马Java——IO流
一、IO流的概述 IO流:存储和读取数据的解决方案 IO流和File是息息相关的 1、IO流的分类 1.1、纯文本文件 word、Excel不是纯文本文件 而txt或者md文件是纯文本文件 2、小结 二、IO流的体系结构 三、字节流 1、FileOutputStream(字节输出流ÿ…...
re:从0开始的CSS学习之路 11. 盒子垂直布局
1. 盒子的垂直布局的注意 若两个“相邻”垂直摆放的盒子,上面盒子的下外边距与下面盒子的上外边距会发生重叠,称为外边距合并 若合并后,外边距会选择重叠外边距的较大值 若两个盒子具有父子关系,则两个盒子的上外边距会发生重叠&…...
Kindling-OriginX 如何集成 DeepFlow 的数据增强网络故障的解释力
DeepFlow 是基于 eBPF 的可观测性开源项目,旨在为复杂的云基础设施及云原生应用提供深度可观测性。DeepFlow 基于 eBPF 采集了精细的链路追踪数据和网络、应用性能指标,其在网络路径上的全链路覆盖能力和丰富的 TCP 性能指标能够为专业用户和网络领域专家…...
轻松掌握Jenkins执行远程window的Jmeter接口脚本
Windows环境:10.1.2.78 新建与配置节点 【系统管理】—【管理节点】—【新建节点】输入节点名称,勾选“dumb slave”,点击ok 按如上配置: 说明: Name:定义slave的唯一名称标识,可以是任意字…...
UI文件原理
使用UI文件创建界面很轻松很便捷,他的原理就是每次我们保存UI文件的时候,QtCreator就自动帮我们将UI文件翻译成C的图形界面创建代码。可以通过以下步骤查看代码 到工程编译目录,一般就是工程同级目录下会生成另一个编译目录,会找到…...
OS设备管理
设备管理 操作系统作为系统资源的管理者,其提供的功能有:处理机管理、存储器管理、文件管理、设备管理。其中前三个管理都是在计算机的主机内部管理其相对应的硬件。 I/O设备 I/O即输入/输出。I/O设备即可以将数据输入到计算机,或者可以接收…...
Matlab绘图经典代码大全:条形图、极坐标图、玫瑰图、填充图、饼状图、三维网格云图、等高线图、透视图、消隐图、投影图、三维曲线图、函数图、彗星图
学会 MATLAB 中的绘图命令对初学者来说具有重要意义,主要体现在以下几个方面: 1. 数据可视化。绘图命令是 MATLAB 中最基本也是最重要的功能之一,它可以帮助初学者将数据可视化,更直观地理解数据的分布、变化规律和趋势。通过绘制图表,可以快速了解数据的特征,从而为后续…...
姿态传感器MPU6050模块之陀螺仪、加速度计、磁力计
MEMS技术 微机电系统(MEMS, Micro-Electro-Mechanical System),也叫做微电子机械系统、微系统、微机械等,指尺寸在几毫米乃至更小的高科技装置。微机电系统其内部结构一般在微米甚至纳米量级,是一个独立的智能系统。 微…...
MySQL 基础知识(一)之数据库和 SQL 概述
目录 1 数据库相关概念 2 数据库的结构 3 SQL 概要 4 SQL 的基本书写规则 1 数据库相关概念 数据库是将大量的数据保存起来,通过计算机加工而成的可以进行高效访问的数据集合数据库管理系统(DBMS)是用来管理数据库的计算机系统…...
挑战杯 wifi指纹室内定位系统
简介 今天来介绍一下室内定位相关的原理以及实现方法; WIFI全称WirelessFidelity,在中文里又称作“行动热点”,是Wi-Fi联盟制造商的商标做为产品的品牌认证,是一个创建于IEEE 802.11标准的无线局域网技术。基于两套系统的密切相关ÿ…...
Midjourney提示词风格调试测评
在Midjourney中提示词及风格参数的变化无疑会对最终的作品产生影响,那影响具体有多大?今天我我们将通过一个示例进行探究。 示例提示词: 计算机代码海洋中的黄色折纸船(图像下方)风格参考:金色长发的女人,…...
Codeforces Round 926 (Div. 2)(A~C)
A. Sasha and the Beautiful Array 分析:说实话,打比赛的时候看到这题没多想,过了一下样例发现将数组排序一下就行,交了就过了。刚刚写题解反应过来,a2-a1a3-a2.....an-a(n-1) an - a1,所以最后结果只取决…...
Godot 游戏引擎个人评价和2024年规划(无代码)
文章目录 前言Godot C# .net core 开发简单评价Godot相关网址可行性 Godot(GDScirpt) Vs CocosGodot VS UnityUnity 的裁员Unity的股票Unity的历史遗留问题:Mono和.net core.net core的开发者,微软 个人的独立游戏Steam平台分成说明独立游戏的选题美术风…...
Win11关闭Windows Defender实时保护,暂时关闭和永久关闭方法 | Win10怎么永久关闭Windows Defender实时保护
文章目录 1. 按2. 暂时关闭Windows Defender实时保护3. 永久关闭实时保护 1. 按 开启Windows Defender实时保护有时候会导致系统变得异常卡顿,严重影响系统的流畅度,并且由于会有几率错误拦截和查杀我们的正常操作,所以还会导致我们的程序无…...
C# CAD2016 宗地生成界址点,界址点编号及排序
1 、界址点起点位置C# CAD2016 多边形顶点按方向重新排序 2、 界址点顺时针逆时针走向 C# CAD2016 判断多边形的方向正时针或逆时针旋转 3、块文件插入 //已知块文件名称 GXGLQTC //块文件需要插入的坐标点 scaledPoint// 插入块到当前图纸中的指定位置ObjectId newBlockId;B…...
[ai笔记7] google浏览器ai学习提效定制优化+常用插件推荐
欢迎来到文思源想的ai空间,这是技术老兵重学ai以及成长思考的第7篇分享! 工欲善其事必先利其器,为了ai学习的效能提升,放假期间对google浏览器做了一次系统整改,添加了一些配置和插件,这里既有一些显示、主…...
联想thinkpad-E450双系统升级记
早期笔记本联想thinkpad-E450双系统 大约16年花4000多大洋,买了一台thinkpad-E450屏幕是16寸本,有AMD独立显卡,i5cpu,4G内存。 . 后来加了一个同型号4G内存组成双通道, . 加了一个三星固态500G, . 换了一个…...