蓝桥杯--平均
在编程竞赛,尤其是参与蓝桥杯的过程中,遇到各种问题需求是家常便饭。最近,我遇到了一个非常有趣且颇具挑战性的算法问题。问题描述如下:对于一个长度为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排序机…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
