蓝桥杯每日真题 - 第10天

embedded/2024/11/14 21:03:30/

题目:(班级活动)

题目描述(14届 C&C++ B组C题)

7d0e93d676104795ba2f1086e92eeac2.png

解题思路:

题目要求我们找到最小的修改次数,使得任意一名同学的 ID 都与另一名同学的 ID 不相同。可以总结出这是一个寻找“重复数字最少修改次数”的问题。我们可以按照以下思路来解决:

  1. 统计频次:遍历学生的 ID 列表,统计每个 ID 出现的次数。

  2. 处理重复 ID:对于每一个出现次数超过 1 的 ID,需要将多余的 ID 修改为未出现的 ID。

  3. 贪心选择未使用的 ID:我们可以将重复的 ID 替换为一个在 [1, n] 范围内未使用的 ID。

代码实现(C语言):

#include <stdio.h>int main() {int n;scanf("%d", &n);int ids[n];int count[100001] = {0};  // 假设每个 id 范围在 [1, 100000],足够存储频次// 读取输入并统计频次for (int i = 0; i < n; i++) {scanf("%d", &ids[i]);count[ids[i]]++;}int modifications = 0;int nextAvailableId = 1;for (int i = 0; i < n; i++) {while (count[ids[i]] > 1) {  // 当前 id 有重复// 找到一个未被使用的 idwhile (nextAvailableId <= n && count[nextAvailableId] > 0) {nextAvailableId++;}// 替换重复 id,并更新计数count[ids[i]]--;count[nextAvailableId]++;modifications++;}}printf("%d\n", modifications);return 0;
}
 ​​​​

代码分析: 

  • 统计频次:使用 count 数组记录每个 ID 的出现次数,遍历时将重复的 ID 进行计数。

  • 贪心选择未使用的 ID:设置 nextAvailableId,每当遇到重复 ID 时,找到下一个未使用的 ID 并进行替换。

  • 计数修改次数:每次替换重复 ID 后,增加 modifications 的计数。

得到运行结果:

e9559abf660f4f498bfc77215f45519b.png

难度分析

⭐️⭐️ 

总结

通过统计 ID 频次并使用贪心策略选择未使用的 ID,可以高效解决重复 ID 的替换问题,使得每个 ID 在数组中唯一。


http://www.ppmy.cn/embedded/137592.html

相关文章

css实现div被图片撑开

固定好盒子的宽度&#xff0c;高度随传过来的图片大小决定 <div class"tab-con"> <img:src"concertInfo.detail"alt""> </div>.tab-con {margin-bottom: 20px;width: 700px;img {width: 700px;height: auto;object-fit: cont…

SpringCloud学习笔记

SpringCloud 在微服务中&#xff0c;不同的服务板块是分开的&#xff0c;有自己的数据库。但是在业务中可能存在服务板块中互相调用的情况&#xff0c;比如订单服务中需要获取用户信息&#xff0c;这时候不能再自己的板块中直接进行查询&#xff0c;否则违反了微服务的理念&am…

深入探讨 .NET Core 3.0 浮点计算差异与解决方案

在 .NET Core 3.0 中&#xff0c;对浮点解析和格式进行了更改&#xff0c;以符合 IEEE 754-2008 标准。您可以在这篇文章中阅读有关这些更改的更多信息。在使用 Stimulsoft 产品时&#xff0c;这些更改最常表现为舍入数字和出现“负号”零。 Stimulsoft Ultimate &#xff08;…

微服务相关问题

什么是雪崩 1、微服务相互调用&#xff0c;服务提供者出现故障或阻塞&#xff1b; 2、服务调用者没有做好异常处理&#xff0c;导致自身故障&#xff1b; 3、调用链中的所有服务级联失败&#xff0c;导致整个集群故障&#xff1b; 解决思路 1、尽量避免服务出现故障或阻塞&…

matlab生成m序列(数字图像水印相关)

m序列 定义 m序列是一种重要的伪随机序列&#xff08;PN序列&#xff09;&#xff0c;它是由线性反馈移位寄存器产生的周期最长的序列&#xff0c;其规律性强&#xff0c;有很好的自相关性和较好的互相关特性。 周期由什么决定&#xff1f; 既然m序列是周期最长的序列&…

C#封装EPPlus库为Excel导出工具

1&#xff0c;添加NUGet包 2&#xff0c;封装工具类 using OfficeOpenXml; using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Reflection;namespace GMWPF.utils {public class ExcelUtil<T>{/// <summary>///…

什么是 ISP:了解互联网服务提供商的作用

一、ISP 基础知识 从本质上讲&#xff0c;ISP 提供两项主要服务&#xff1a;互联网接入和互联网传输。互联网接入是指使用户能够连接到互联网的物理和逻辑连接&#xff0c;通常通过调制解调器、路由器或其他网络设备。此连接可以是有线的&#xff08;例如通过 DSL、光纤或电缆…

使用element UI实现表格行/列合并

前言 本文代码使用vue2element UI&#xff0c;通过给table传入span-method方法实现合并行或列 效果图 示例代码 后端返回数据格式如下 {"total": 12,"records": [[{"id": 1,"project": "田径","subitem": &qu…