蓝桥杯--平均
在编程竞赛,尤其是参与蓝桥杯的过程中,遇到各种问题需求是家常便饭。最近,我遇到了一个非常有趣且颇具挑战性的算法问题。问题描述如下:对于一个长度为n的数组(n是10的倍数),数组中的每个元素均为区间内的整数。任务是通过对数组中的元素进行调整,使得每个元素出现的次数都相同(即每种数各出现n/10次),同时需要保证调整的总代价最小。
在初始阶段,我差点就被这个问题难住了。问题本身看似简单——让每种数字出现频率相等,但实际要找到最小代价的实现却需要深思熟虑的策略。毕竟,单纯的试错代价过于巨大,我们必须要有明确的方向性。
算法思路如下:
- 首先需要对数组中的每个数字进行计数,明确各数字出现的次数。
- 其次,要明确每次更改操作的代价。这意味着我们需要为数组中的每个元素
ai记录一个更改代价bi。 - 然后考虑如何以最小代价达到目标状态。由于频率超出或低于目标频率n/10的元素都需要调整,因此我们需要采取一个有效策略,以保证在必要时优先调整代价最小的元素。
解决方案:
我采用了贪心算法来逐渐接近目标状态。贪心算法在多种情况下都极为有效,尤其是在需要进行多步决策的问题中,我们可以在每一步选择当前最优的解决方案。
为了实现这个策略,我创建了一个按照bi排序的元素列表来保证在调整过程中,我们总是优先选择调整代价较低的元素。通过不断的选择最小代价的元素进行调整,我得以逐步使每个数字的出现次数向目标值n/10靠近,直至达成平衡。
在编程实践中,我遇到了一些边缘情况,比如当多个数字的出现次数都超出或低于目标频率n/10时,选择哪一个调整就变得更为微妙,我不得不在算法中添加额外的逻辑来处理这些情况。
在无数次的调试、优化后,我的算法成功通过了所有测试用例,并且在实际比赛中取得了不错的成绩。这个问题不仅提升了我的算法设计能力,更重要的是教会了我在面对挑战时不断探索和实践的重要性。
import java.util.*;public class BalanceArray {static class Pair {int num;int cost;Pair(int num, int cost) {this.num = num;this.cost = cost;}}public static int minCostToBalance(int[] nums, int[] costs) {int n = nums.length;int target = n / 10;int totalCost = 0;int[] frequency = new int[10];List<Pair> pairs = new ArrayList<>();// 统计每个数字的出现频率,并创建代价数组for (int i = 0; i < n; i++) {frequency[nums[i]]++;pairs.add(new Pair(nums[i], costs[i]));}// 按照代价进行排序pairs.sort(Comparator.comparingInt(pair -> pair.cost));// 调整频率高于和低于目标的数,使得频率达到平衡for (int i = 0; i < pairs.size(); i++) {Pair p = pairs.get(i);while (frequency[p.num] > target) {frequency[p.num]--;totalCost += p.cost;}}// 若有数频率仍然过低,需要从已降低数的集合中选择最小代价和进行调整for (int i = 0; i < pairs.size(); i++) {Pair p = pairs.get(i);while (frequency[p.num] < target) {frequency[p.num]++;totalCost += p.cost;}}return totalCost;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] nums = new int[n];int[] costs = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();costs[i] = scanner.nextInt();}scanner.close();int result = minCostToBalance(nums, costs);System.out.println(result);}
}
总结我的学习经历,关键在于理解了算法不仅是编程的一项基本技能,更是一种可应用于各类问题解决的工具。勇于尝试、耐心思考和有效调整是走向成功的重要步骤。
随着时间的推进,我对算法的理解将会更加深入,而我相信,在这个过程中,我不仅会成为一个更出色的程序员,也将不断增强解决实际问题的能力。在未来的编程之路上,我期待遇到更多的挑战,而这个问题无疑已经为我铺设了一段坚实的基石。
相关文章:
蓝桥杯--平均
在编程竞赛,尤其是参与蓝桥杯的过程中,遇到各种问题需求是家常便饭。最近,我遇到了一个非常有趣且颇具挑战性的算法问题。问题描述如下:对于一个长度为n的数组(n是10的倍数),数组中的每个元素均…...
未来已来:科技驱动的教育变革
我们的基础教育数百年来一成不变。学生们齐聚在一个物理空间,听老师现场授课。每节课时长和节奏几乎一致,严格按照课表进行。老师就像“讲台上的圣人”。这种模式千篇一律,并不适用于所有人。学生遇到不懂的问题,只能自己摸索或者…...
【蓝桥杯每日一题】填充颜色超详细解释!!!
为了让蓝桥杯不变成蓝桥悲,我决定在舒适的周日再来一道题。 例: 输入: 6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 输出: 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1…...
VSCODE的常用插件
1、中文设置 (1)搜索 chinese Chinese (Simplified) Language Pack for Visual Studio Code C/C Extension Pack (2)配置 通过使用“Configure Display Language”命令显式设置 VS Code 显示语言,可以替代默认 UI…...
Oracle常用DBA相关语句
Oracle常用DBA相关语句 1 表空间1.1 创建表空间1.2 删除表空间1.3 收缩表空间1.4 新增表空间文件1.5 查看表空间使用情况1.6 查看表所占用的空间大小 2 表分区2.1 查询表分区的创建情况2.2 查询表时指定分区 3 用户3.1 创建用户3.2 给用户赋权限3.3 删除用户 4 导入导出4.1 导入…...
JavaScript 入门指南(一)简介及基础语法
JavaScript 简介 JavaScript,简称 js,是一种基于对象(object-based)和事件驱动(Event Driven)的简单的并具有安全性能的脚本语言。 JavaScript 特性 JavaScript 是解释性语言,而不是编译性语言…...
UbuntuServer22.04配置静态IP地址
查看网络配置文件 使用命令, 查看网络配置文件 ls -l /etc/netplan/输出如下(文件名可能不同, 以实际查询为准) -rw------- 1 root root 191 Mar 17 03:30 00-installer-config.yaml编辑文件即可修改网络配置 sudo vim /etc/netplan/00-installer-config.yaml配…...
vue3 打印局部网页、网页下载为图片、下载为pdf-自动分页,几行代码搞定
经常有一些需求,要将网页保存为一张图片,感觉异常困难,这里发现一个简单的办法。 这么简单,直接一句哇塞,老板:马上完成任务。 先安装几个依赖 npm i howuse html2canvas jspdf 下载图片代码 <button …...
力扣hot100:34. 在排序数组中查找元素的第一个和最后一个位置(二分查找的理解)
我们知道使用二分查找能找到值所在的位置。假如我们在找到值后仍然不断的更新指针会发生什么?我们可以利用这一点来找到最左边的以及最右边的值。 如果当nums[mid]target时,使得 rightmid-1,那么最终会使得target在right的右边。 如果当nums[…...
几何相互作用GNN预测3D-PLA
预测PLA是药物发现中的核心问题。最近的进展显示了将ML应用于PLA预测的巨大潜力。然而,它们大多忽略了复合物的3D结构和蛋白质与配体之间的物理相互作用,而这对于理解结合机制至关重要。作者提出了一种结合3D结构和物理相互作用的几何相互作用图神经网络GIGN,用于预测蛋白质…...
2024最新版使用PyCharm搭建Anaconda
2024最新版使用PyCharm搭建Anaconda 因为pycharm自带的包不全,或者下载的时候比较慢,所以我们直接用anaconda的包,毕竟我们以后还会学到很多的包,不多说,直接开干! 一、下载Pycharm、Anacoda pycharm中文网…...
前台于后台项目
一:技术栈 前台:vue3element plus 后台:reactant desgin 二:项目中的问题: 多人协同开发导致样式冲突 ui框架中组件的使用 ui框架中组件样式的修改 精度缺失问题 框架的使用 三:解决方案: …...
Magical Combat VFX
这个包包含30个可供游戏使用的VFX,有各种口味,为您的游戏增添趣味! 所有VFX都经过了很好的优化,可以在所有平台上使用。 这个包特别有一堆闪电魔法,有两种主要的变体,一种是深色的,另一种是浅色的。但它也提供了一系列其他视觉效果,如神圣咒语、音乐主题等等! 我们提供…...
hadoop伪分布式环境搭建详解
(操作系统是centos7) 1.更改主机名,设置与ip 的映射关系 hostname //查看主机名 vim /etc/hostname //将里面的主机名更改为master vim /etc/hosts //将127.0.0.1后面的主机名更改为master,在后面加入一行IP地址与主机名之间的…...
day12-SpringBootWeb 登录认证
一、登录功能 Slf4j RestController public class LoginController {Autowiredprivate EmpService empService;PostMapping("/login")public Result login(RequestBody Emp emp){log.info("员工登录: {}", emp);Emp e empService.login(emp);//登录失败, …...
内外网数据单向导入导出 如何提升效率确保安全性?
金融、证券、税务、海关、军工、国央企、生物医药等涉密行业,为了保护内部的核心数据,都会将网络进行物理隔离,网络物理隔离主要是采用隔离硬件设备,在人工或者软件的控制下,进行内外网的切换和数据交换。 传统的内外网…...
Spring核心方法:Refresh全解(WebMVC如何装配、关联)
Spring核心方法:Refresh全解(WebMVC如何装配、关联) 这里是一个表格,列出了Spring容器刷新过程中执行的方法以及它们的作用: 方法名称描述prepareRefresh()初始化一些属性和状态,例如启动时间戳、活动标志、环境变量等。obtainF…...
TCP:三次握手四次挥手及相关问题:
连接—三次握手: 流程图: 过程详解: 客户端(connect)连接服务器(listen) Client将标志位SYN置为1,随机产生一个值seqx, 并将该数据包发送给Server, Client进入SYN_ SENT状态,等待Server确认。Server收到数据包后由标…...
链式二叉树--前序中序后序遍历,高度,节点个数问题
目录 前言: 一:链式二叉树的结构定义 二:链式二叉树的遍历--->前序,中序,后序 1.前序 递归展开图分析 2.中序 递归展开图分析 3.后序 三:二叉树结点的求解 1.二叉树总结点 递归展开分析 2…...
HCIA——TCP协议详解
目录 1、TCP概念及协议头部格式 1.1TCP特点 1.2TCP协议协议头部格式 1.3字段进行介绍 1.3.1源端口和目的端口 1.3.2序号(seq) 1.3.3确认序号(ack) 1.3.4数据偏移 1.3.5标志位 1.3.6窗口 1.3.7校验和 1.3.8紧急指针 2、TCP的可靠性 2.1 TCP可靠性的保障 2.2排序机…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
Java数组Arrays操作全攻略
Arrays类的概述 Java中的Arrays类位于java.util包中,提供了一系列静态方法用于操作数组(如排序、搜索、填充、比较等)。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序(sort) 对数组进行升序…...
