贪心算法练习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…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
