当前位置: 首页 > news >正文

练习-班级活动(map存储键值对)

问题描述

小明的老师准备组织一次班级活动。班上一共有 n 名 (n 为偶数) 同学,老师想把所有的同学进行分组,每两名同学一组。为了公平,老师给每名同学随机分配了一个 n 以内的正整数作为 id,第 i 名同学的 id 为 ai​。

老师希望通过更改若干名同学的 id 使得对于任意一名同学 i,有且仅有另一名同学 j 的 id 与其相同 (ai=aj)。请问老师最少需要更改多少名同学的 id?

输入格式

输入共 2 行。

第一行为一个正整数 n。

第二行为 n 个由空格隔开的整数 a1,a2,...,an​。

输出格式

输出共 1 行,一个整数。

样例输入

4
1 2 2 3

样例输出

1

样例说明

仅需要把 a1​ 改为 3 或者把 a3 改为 1 即可。

评测用例规模与约定

解题代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];                // 存储每个同学的 id
map<int, int> m;         // 统计每个 id 出现的次数int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];m[a[i]]++;       // 统计每个 id 出现的次数}int cnt1 = 0;        // 统计出现次数为 1 的 id 数量int cnt2 = 0;        // 统计出现次数大于 2 的 id 中需要更改的数量int cnt = 0;         // 最终需要更改的 id 数量// 遍历 map,统计 cnt1 和 cnt2for (auto& pair : m) {if (pair.second == 1) {cnt1++;      // 统计出现次数为 1 的 id 数量} else if (pair.second > 2) {cnt2 += (pair.second - 2); // 统计出现次数大于 2 的 id 中需要更改的数量}}//判断更改的总数//若大于2 的ID总数大于等于1 的//最后和1配对完的所有数均要更改if(cnt2>cnt1){cnt=cnt2;}//若大于2 的ID总数小于等于1 的//最后等于1的两两配对else{cnt=(cnt1-cnt2)/2+cnt2;}cout << cnt ; return 0;
}

1. 理解问题

  • 目标:将 n 名同学分成 n/2 组,每组两人的 id 相同。

  • 限制:每个 id 出现的次数必须是偶数次(即每个 id 出现两次)。

  • 操作:通过更改某些同学的 id,使得所有 id 的出现次数满足上述条件。


2. 分析 id 出现次数的分布

  • 统计每个 id 出现的次数。

  • 将 id 的出现次数分为以下几类:

    1. 出现次数为 1:这些 id 必须被更改,因为无法单独成对。

    2. 出现次数为 2:这些 id 已经满足条件,无需更改。

    3. 出现次数大于 2:这些 id 需要减少出现次数,使其变为 2。


3. 确定需要更改的 id 数量

  • 出现次数为 1 的 id

    • 这些 id 必须被更改,因为无法单独成对。

    • 如果有 cnt1 个出现次数为 1 的 id,则需要至少 cnt1 / 2 次更改(两两配对)。

  • 出现次数大于 2 的 id

    • 这些 id 需要减少出现次数,使其变为 2。

    • 如果一个 id 出现 k 次(k > 2),则需要更改 k - 2 次。

  • 综合计算

    • 如果出现次数大于 2 的 id 需要更改的总次数 cnt2 大于等于出现次数为 1 的 id 数量 cnt1,则总更改次数为 cnt2

    • 否则,总更改次数为 (cnt1 - cnt2) / 2 + cnt2

4. 代码分析注释

  1. 输入数据

    • 使用数组 a[N] 存储每个同学的 id

    • 使用 map<int, int> m 统计每个 id 出现的次数。

  2. 统计 id 出现次数

    • 遍历数组 a,将每个 id 的出现次数记录在 map 中。

  3. 统计 cnt1 和 cnt2

    • cnt1:统计出现次数为 1 的 id 数量。

    • cnt2:统计出现次数大于 2 的 id 中需要更改的数量。例如,如果一个 id 出现 4 次,则需要更改 4 - 2 = 2 次。

  4. 计算需要更改的 id 数量

    • 情况 1:如果 cnt2 >= cnt1,即出现次数大于 2 的 id 数量大于等于出现次数为 1 的 id 数量,则需要更改的总数为 cnt2

    • 情况 2:如果 cnt2 < cnt1,则需要将多余的 cnt1 - cnt2 个出现次数为 1 的 id 两两配对,每对需要更改 1 次,因此总更改次数为 (cnt1 - cnt2) / 2 + cnt2

  5. 输出结果

    • 输出需要更改的 id 数量。

相关文章:

练习-班级活动(map存储键值对)

问题描述 小明的老师准备组织一次班级活动。班上一共有 n 名 (n 为偶数) 同学&#xff0c;老师想把所有的同学进行分组&#xff0c;每两名同学一组。为了公平&#xff0c;老师给每名同学随机分配了一个 n 以内的正整数作为 id&#xff0c;第 i 名同学的 id 为 ai​。 老师希望…...

34-三数之和

给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组。 方法一&…...

Excel online开始支持Copilot高级数据分析:Python提供强大的数据见解

前文讲过Excel中的copilot可以直接调用Python进行高级数据分析&#xff1a; Copilot&#xff1a;Excel中的Python高级分析来了 Python in Excel高级分析&#xff1a;一键RFM分析 超越DeepSeek&#xff1a;Copilot in Excel高级数据分析原生支持Python无需安装软件 零代码、…...

【数据结构】kmp算法介绍+模板代码

目录 1.kmp算法介绍 2.应用场景 3.KMP与暴力算法比较 4.模板代码 KMP算法是一种高效的字符串匹配算法&#xff0c;用于在文本串中快速查找模式串的所有出现位置。其核心思想是通过预处理模式串&#xff0c;避免在匹配失败时进行不必要的回溯&#xff0c;从而将时间复杂度优…...

python关键字汇总

文章目录 1. 变量与类型相关2. 控制流相关3. 函数与类相关4. 异常处理相关5. 模块相关6. 其他 在 Python 3 里有 35 个关键字&#xff0c;它们各自具备特定的用途与意义 1. 变量与类型相关 True、False 意义&#xff1a;布尔类型的常量&#xff0c;分别代表逻辑真与逻辑假。示…...

六十天前端强化训练之第二十五天之组件生命周期大师级详解(Vue3 Composition API 版)

欢迎来到编程星辰海的博客讲解 看完可以给一个免费的三连吗&#xff0c;谢谢大佬&#xff01; 目录 一、生命周期核心知识 1.1 生命周期全景图 1.2 生命周期钩子详解 1.2.1 初始化阶段 1.2.2 挂载阶段 1.2.3 更新阶段 1.2.4 卸载阶段 1.3 生命周期执行顺序 1.4 父子组…...

油候插件、idea、VsCode插件推荐(自用)

开发软件&#xff1a; 之前的文章&#xff1a; 开发必装最实用工具软件与网站 推荐一下我使用的开发工具 目前在用的 油候插件 AC-baidu-重定向优化百度搜狗谷歌必应搜索_favicon_双列 让查询变成多列&#xff0c;而且可以流式翻页 Github 增强 - 高速下载 github下载 TimerHo…...

R语言基于ggscitable包复现一篇3.5分的文章的连续变量交互效应(交互作用)的可视化图

交互作用效应(p for Interaction)在SCI文章中可以算是一个必杀技&#xff0c;几乎在高分的SCI中必出现&#xff0c;因为把人群分为亚组后再进行统计可以增强文章结果的可靠性&#xff0c;进行可视化后可以清晰的表明变量之间的关系。不仅如此&#xff0c;交互作用还可以使用来进…...

mac环境下chatwoot客服聊天docker本地部署+对接通义千问Qwen2.5

&#x1f680; 安装docker-desktop &#x1f680; 定义一个.env环境变量文件docker-compose.yaml .env # Learn about the various environment variables at # https://www.chatwoot.com/docs/self-hosted/configuration/environment-variables/#rails-production-variables…...

mac上安装nvm及nvm的基本语法使用!!

种一棵树&#xff0c;最好是十年前&#xff0c;其次是现在&#xff01;想要改变&#xff0c;从此刻开始&#xff0c;一切都不晚&#xff01; 目录 nvm是什么&#xff1f;前提条件&#xff1a;安装homebrew如果系统已经有node版本&#xff1a;在mac上安装nvm&#xff1a;用nvm安…...

论文阅读:2024-NAACL Semstamp、2024-ACL (Findings) k-SemStamp

总目录 大模型安全相关研究:https://blog.csdn.net/WhiffeYF/article/details/142132328 Semstamp: A semantic watermark with paraphrastic robustness for text generation https://aclanthology.org/2024.naacl-long.226/ k-SemStamp: A Clustering-Based Semantic Wate…...

本地JAR批量传私服

在有网络隔离的环境下&#xff0c;Maven项目如果没有搭建私服就得把用到的通用组件通过U盘在每个组员间拷贝来拷贝去。非常的麻烦跟低效。搭建私服&#xff0c;如果通用组件很多的时候手工一个一个上传更是非常的麻烦跟低效&#xff1b; 我就遇上这问题&#xff0c;跟A公司合作…...

Linux上位机开发实战(camera视频读取)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 关于linux camera&#xff0c;一般都是认为是mipi camera&#xff0c;或者是usb camera。当然不管是哪一种&#xff0c;底层的逻辑都是v4l2&#x…...

OpenCV图像处理基础1

OpenCV 提供了丰富的图像处理和计算机视觉功能,包括图像读取、显示、颜色空间转换、滤波、边缘检测、轮廓检测等。 本章将介绍 OpenCV 的基本概念和常用功能。 图像的表示和处理 OpenCV 通过 NumPy 数组 来表示图像数据,每个图像就是一个多维数组,其中每个元素对应图像中的…...

Python Web 框架 Django、Flask 和 FastAPI 对比

在探索 Python Web 框架时&#xff0c;Django、Flask 和 FastAPI 无疑是最常被提及的名字。根据我们最新的 Python 开发者调查&#xff0c;这三大框架继续稳坐后端 Web 开发的热门宝座。它们均为开源项目&#xff0c;并且与 Python 的最新版本无缝兼容。然而&#xff0c;面对不…...

TISAX认证注意事项的详细介绍

TISAX&#xff08;Trusted Information Security Assessment Exchange&#xff09;认证的注意事项犹如企业在信息安全领域航行时必须遵循的灯塔指引&#xff0c;至关重要且不容忽视。以下是对TISAX认证注意事项的详尽阐述&#xff1a; 首先&#xff0c;企业需深入研读并理解TI…...

JavaScript |(六)DOM事件 | 尚硅谷JavaScript基础实战

学习来源&#xff1a;尚硅谷JavaScript基础&实战丨JS入门到精通全套完整版 笔记来源&#xff1a;在这位大佬的基础上添加了一些东西&#xff0c;欢迎大家支持原创&#xff0c;大佬太棒了&#xff1a;JavaScript |&#xff08;六&#xff09;DOM事件 | 尚硅谷JavaScript基础…...

【动态规划】详解混合背包问题

目录 1. 前置文章2. 题目3. 小结 1. 前置文章 本文前置文章&#xff1a; 【动态规划】详解 0-1背包问题【动态规划】详解完全背包问题【动态规划】详解分组背包问题【动态规划】详解多重背包问题 下面是三种背包模式的区别&#xff1a; 0 - 1 背包 是说&#xff1a;有 n 个…...

Nodejs 项目打包部署方式

方式一&#xff1a;PM2 一、准备工作 确保服务器上已安装 Node.js 环境建议使用 PM2 进行进程管理&#xff08;需要额外安装&#xff09; 二、部署步骤 1.首先在服务器上安装 PM2&#xff08;推荐&#xff09;&#xff1a; npm install -g pm22.将项目代码上传到服务器&…...

银河麒麟操作系统的上下游版本判断

以下内容摘自《银河麒麟操作系统进阶应用》一书。 几百款Linux发行版之间并不是完全独立的&#xff0c;绝大多数Linux发行版可以追溯到几个关键的“祖先”发行版&#xff0c;其中最为人熟知的包括Debian、Fedora、Slackware和Arch Linux。这些“祖先”发行版又称“原始”发行版…...

Retrofit中scalars转换html为字符串

简介 在Retrofit中&#xff0c;如果你想直接获取HTML或其他文本格式的响应内容而不是将其映射到一个模型类&#xff0c;ScalarsConverterFactory 就派上用场了。ScalarsConverterFactory 是一个转换器工厂&#xff0c;它能够将响应体转换为Java基本类型如String、Integer或Byte…...

Java基础面试题学习

转换成自已的语言来回答&#xff0c;来源小林coding、沉默王二以及其它资源和自已改编。 1、概念 1、说一下Java的特点 我认为Java有很多特点 首先是平台无关性&#xff1a;Java可以实现一次编译到处运行&#xff0c;因为Java的编译器将源代码编译成字节码&#xff0c;使得该…...

# [RPA] 使用八爪鱼进行高效网页数据采集

在许多行业中&#xff0c;数据是核心资产。然而&#xff0c;虽然许多网站的文本内容可以免费访问&#xff0c;但手动一条一条采集&#xff0c;不仅耗时耗力&#xff0c;还容易出错。这种情况下&#xff0c;使用自动化工具来提高采集效率就显得尤为重要。本文将介绍 八爪鱼 这一…...

【工具变量】全国地级市地方ZF债务数据集(2014-2023年)

地方ZF债务是地方财政运作的重要组成部分&#xff0c;主要用于基础设施建设、公共服务及经济发展&#xff0c;是衡量地方财政健康状况的重要指标。近年来&#xff0c;我国地级市的地方ZF债务规模不断变化&#xff0c;涉及一般债务和专项债务等多个方面&#xff0c;对金融市场、…...

6.5840 Lab 3: Raft

论文很重要 raft-zh_cn/raft-zh_cn.md at master maemual/raft-zh_cn GitHub Part 3A: leader election (moderate) 十次test都过了 实现 Raft 的领导者选举和心跳机制&#xff08;AppendEntries RPC&#xff0c;无日志条目&#xff09;。第 3A 部分的目标是实现以下功能&am…...

DCDC36V同步降压 输出可调 2A电流恒压芯片SL1588H 替换LV3842

在当今电子设备飞速发展的时代&#xff0c;电源管理芯片的性能优劣直接关乎设备的稳定性与高效运行。对于诸多需要将 36V 电压进行同步降压、输出电压可调且稳定输出 2A 电流的应用场景&#xff0c;一款卓越的恒压芯片不可或缺。SL1588H 正凭借其领先的技术和出色的性能&#x…...

AH4953A双PMOS管深度解析:无线充系统的“高效开关”设计实践

AH4953 30v5A双PMOS管深度解析&#xff1a;无线充系统的“高效开关”设计实践 1. 产品定位与基础特性 AH4953A双通道P沟道MOSFET&#xff0c;专为无线充电、电源管理等高频开关场景优化。其核心优势体现在&#xff1a; • 高耐压低损耗&#xff1a;30V漏源电压&#xff08;Vd…...

图数据库Neo4j和JDK安装与配置教程(超详细)

目录 前言 一、Java环境配置 &#xff08;一&#xff09;JDK的下载与安装 &#xff08;二&#xff09;JDK环境配置 &#xff08;三&#xff09;检测JDK17是否配置成功 二、Neo4j的安装与配置 &#xff08;一&#xff09;Neo4j的下载与安装 &#xff08;二&#xff09;N…...

现代美学工业风品牌海报徽标设计PSAI无衬线英文字体安装包 Moldin – Condensed Sans Serif Font

现代几何工业风品牌海报徽标设计无衬线英文字体安装包 Moldin — Condensed Sans Serif Font Moldin 是一个粗体浓缩的无衬线字体系列&#xff0c;旨在为显示和标题提供最大的影响。Moldin 有 6 种粗细可供选择&#xff0c;从常规到黑色&#xff0c;提供静态和可变格式&#x…...

Excel(函数进阶篇):FILTER函数全解读、XLOOKUP函数全解读、UNIQUE函数、数组与数组公式

目录 数组与数组函数office365中VLOOKUP函数的加强数组中的多条件判断FILTER函数详解用法概述函数语法 基础筛选多条件筛选进阶技巧结合动态数组 高级函数整合错误处理注意事项FILTER经典问题&#xff1a;一对多查询 XLOOKUP函数XLOOKUP基础用法XLOOKUP函数多条件匹配和双向查询…...

django入门教程之request和reponse【二】

接上节&#xff1a;入门【一】 再创建一个orders子应用&#xff0c;python manager.py startapp orders&#xff0c;orders目录中新建一个urls.py文件。结构如图&#xff1a; 通过上节课&#xff0c;我们知道在views.py文件中编写函数时&#xff0c;有一个默认入参request&…...

第十五次CCF-CSP认证(含C++源码)

第十五次CCF-CSP认证 小明上学满分思路 数据中心满分思路 小明放学满分题解 小明上学 题目链接 满分思路 其实题目看着长&#xff0c;但是做起来是非常好写的&#xff0c;其实主要原因在于&#xff0c;他的红绿灯的变化规律是一定的&#xff0c;而且小明路上的每次红绿灯情况…...

Excel处理控件Spire.XLS系列教程:C# 在 Excel 中添加或删除单元格边框

单元格边框是指在单元格或单元格区域周围添加的线条。它们可用于不同的目的&#xff0c;如分隔工作表中的部分、吸引读者注意重要的单元格或使工作表看起来更美观。本文将介绍如何使用 Spire.XLS for .NET 在 C# 中添加或删除 Excel 单元格边框。 安装 Spire.XLS for .NET E-…...

混合精度-基于torch内部

定义 混合精度训练是一种在深度学习模型训练过程中&#xff0c;同时使用不同精度数据类型&#xff08;主要是单精度 FP32 和半精度 FP16&#xff09;来进行计算和存储的技术。以下是具体介绍&#xff1a; 数据类型&#xff1a; 单精度&#xff08;FP32&#xff09;&#xff1…...

Ubuntu16.04网卡ens33找不到异常修复

重启网络 systemctl stop NetworkManager systemctl restart networking允许网络可用 连接网络 验证网络...

C++编译流程

编译器其实就是一个翻译器&#xff0c;把我们的文件内容翻译成机器能够看懂的指令&#xff0c;但如何合理翻译是核心。 C语言编译 需要经过以下几步&#xff1a; 词法分析&#xff1a;扫描代码&#xff0c;确定单词类型&#xff0c;比如是变量还是函数&#xff0c;是标识符还…...

人工智能:企业RAG方案

一、LangChain FAISS、Milvus / Weaviate介绍 在企业 RAG &#xff08;Retrieval-Augmented Generation&#xff09;方案中&#xff0c;LangChain FAISS 和 Milvus / Weaviate 都是用于向量检索&#xff08;Vector Search&#xff09;的核心工具。两者的核心区别在于 存储方…...

【Git流程最佳实践】 开发较大功能时应使用project branch

目录 背景和失败经验名词定义曾经使用project branch犯的错 建立project branch的必要性正确的使用project branch的方法 背景和失败经验 我们曾经使用过project branch&#xff0c;但是后来放弃了 名词定义 特性branch(特性分支)&#xff1a; 在开发跨越新特性的时候会从主…...

线程的概念

目录 线程的概念 创建线程快速验证 物理内存管理 再谈页表 今天我们学习线程的概念 线程的概念 进程是一个指向起来的程序&#xff0c;进程内核数据结构代码和数据&#xff0c;线程称为指向流&#xff0c;执行粒度比进程要更细&#xff0c;是进程内部的一个执行分支&…...

firefly经典蓝牙和QProcess、QFileSystemWatcher记录

QProcess 默认不会启动一个 shell 来解析命令,而是直接调用操作系统的系统调用来启动外部程序。也就是通过fork一个子线程或者exec一个子进程来执行命令。 QProcess的参数模式 QProcess 需要明确指定命令的可执行文件路径或参数列表。 如果命令是一个可执行文件的路径…...

北斗设备启动流程与时长解析

北斗卫星导航系统作为我国自主研发的全球卫星导航系统&#xff0c;广泛应用于交通、通信、农业等多个领域。今天&#xff0c;我们就来详细探讨一下北斗设备的启动流程以及不同启动方式下的时长。 一、北斗设备的启动流程 北斗设备的启动流程可以分为以下几个关键步骤&#xf…...

PyTorch分布式训练中各节点如何通信

深度学习 文章目录 深度学习前言pytorch如何初始化分布式训练怎么知道要使用哪几台机器进行训练的如何根据标识进行初始化&#xff08;init_method&#xff09;如何获取进程的唯一标识rank如何实现数据如何分发 前言 同学们在处理分布式训练时经常会遇到以下几个疑问&#xff…...

又双叒叕Scrapy爬虫相关的面试题及详细解答

Scrapy是Python开发的一个快速、高层次的网络爬虫框架,专注于高效抓取网页并提取结构化数据。其核心设计基于异步处理机制,适合大规模数据采集任务。 文章目录 基础概念1. Scrapy框架的核心组件有哪些?架构与流程2. 描述Scrapy的工作流程核心组件详解3. 如何自定义Item Pipe…...

Docker与K8S是什么该怎么选?

用了很久的容器化&#xff0c;最近突然看到一个问题问&#xff1a; docker和K8S究竟有什么区别&#xff0c;到底该怎么选&#xff1f;我认真思考了一会&#xff0c;发现一时间还真说不明白&#xff0c;于是就研究了一段时间发布今天的博文&#xff01; Docker vs Kubernetes&a…...

FPGA中串行执行方式之计数器控制

FPGA中串行执行方式之计数器控制 使用计数器控制的方式实现状态机是一种简单且直观的方法。它通过计数器的值来控制状态的变化,从而实现顺序逻辑。计数器的方式特别适合状态较少且状态转移是固定的场景。 基本原理 计数器控制的状态机 ​例程1:简单的顺序状态机 以下是一个…...

尝试使用tauri2+Django+React的项目

前言 使用Tauri2前端&#xff0c;本质是进程间的通信。并非前后端。 而想使用nw&#xff0c;先后端打包exe&#xff0c;再和前端打包成exe&#xff0c;并没有完成成功。 而笔者从Tauri中看到这种可能性。很有可能成功基于SeaORMMySQLTauri2ViteReact等的CRUD交互项目-CSDN博…...

用@keyframes-animation来实现动画效果

一、使用规则 keyframes 用于定义动画的关键帧。 animation属性 用于将keyframes动画用于元素上。 二、基本语法 keyframes keyframes xuanZhuan { /*xuanZhuan是动画名字,实现旋转*/0%{transform: rotate(0deg);}50%{transform: rotate(180deg);}100%{transform: rotate(…...

kernel中外部传递参数使用方法

在 Linux 内核模块开发中&#xff0c;module_param(rpc_tdebug, uint, 0600); 表示定义一个可通过外部传递参数进行配置的模块级变量&#xff0c;具体解析如下&#xff1a; ‌参数名称‌ rpc_tdebug 是模块参数的变量名&#xff0c;该变量需在代码中提前声明为静态全局变量&…...

AI赋能流域生态评估:从多源数据融合到服务价值预测的技术突破

流域生态系统服务评价是生态学与地理信息科学的交叉前沿&#xff0c;传统方法受限于数据碎片化与模型解释力不足。本文以‌随机森林-时空图卷积联合模型&#xff08;RF-STGCN&#xff09;‌为核心&#xff0c;结合2022年长江中游实际监测数据&#xff0c;详解AI技术在服务评价中…...

SZU软件工程大学生涯 2022~2026

用于个人面试前自我介绍&#xff0c;防止忘记或谈吐不流利。 面试官您好&#xff0c;我是来自深圳大学计算机与软件学院的软件工程专业的王雅贤。在校期间&#xff0c;我修读了程序设计基础、面向对象程序设计、数据结构、算法分析与设计、操作系统等核心课程&#xff0c;系统…...