第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 试题 C: 班级活动

[蓝桥杯 2023 国 B] 班级活动

【问题描述】

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

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

【输入格式】

输入共 2 2 2 行。
第一行为一个正整数 n n n
第二行为 n n n 个由空格隔开的整数 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,,an

【输出格式】

输出共 1 1 1 行,一个整数。

【样例输入】

4
1 2 2 3

【样例输出】

1

【样例说明】

仅需要把 a 1 a_1 a1 改为 3 3 3 或者把 a 4 a_4 a4 改为 1 1 1 即可。

评测用例规模与约定

  • 对于 20 % 20\% 20% 的数据,保证 n ≤ 1 0 3 n \le 10^3 n103
  • 对于 100 % 100\% 100% 的数据,保证 n ≤ 1 0 5 n \le 10^5 n105

由题目可以想到,我们可以将数列中的数大致分为三种:

1. 刚好有两个学号相同

这种情况不做改变即可符合题意。

2. 有大于两个学号相同

这种情况需要将多的改变为其他学号。

3. 只有一个学号

这种情况需要有多的学号转化成该学号或把该学号转化成另一个只有一个的学号。
那么,他们对答案的贡献分别是:
情况 1:无。
情况 2:ans ← sum1 − 2
情况 3:sum1 + ( sum2 - sum1 ) / 2

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int a[N],cnt[N];int main() 
{int n;cin>>n;for(int i=1;i<=n;i++) {cin>>a[i];cnt[a[i]]++;}int sum1=0,sum2=0;for(int i=1;i<=100000;i++){if(cnt[i]>=2) sum1+=(cnt[i]-2);else sum2+=cnt[i];}if(sum1>sum2) cout<<sum1;else cout<<sum1+(sum2-sum1)/2;return 0;
}

在这里插入图片描述

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144428.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Eclipse环境基于HDFS的API进行开发

文章目录 IOUtils方式读取文件1.文件准备2.下载安装Eclipse3.打开eclipse&#xff0c;新建java项目&#xff0c;添加关于hadoop的一些包4.包内新建类进行开发5.利用打包的方式生成java jar包6.验证代码正确性 其它问题&#xff1a;Exception in thread “main“ java.lang.Unsu…

【前端】ECMAScript6从入门到进阶

【前端】ECMAScript6从入门到进阶 1.ES6简介及环境搭建 1.1.ECMAScript 6简介 &#xff08;1&#xff09;ECMAScript 6是什么 ECMAScript 6.0&#xff08;以下简称 ES6&#xff09;是 JavaScript 语言的下一代标准&#xff0c;已经在2015年6月正式发布了。它的目标&#xff…

基于微信小程序的刷题考试系统设计与实现(适用于各类考试类、答题类程序)

文章目录 前言系统主要功能&#xff1a;具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…

【IDEA】使用idea调试时查看对象集合的值

1、在实体类上添加toString方法 2、在要查看集合的地方右键View as→toString 3、View Text复制对象集合的值 4、复制map集合的值同理

[杂谈]-ESP32中的无线通信协议

ESP32中的无线通信协议 文章目录 ESP32中的无线通信协议1、ESP32 无线通信协议简介2、Bluetooth Low Energy (BLE)3、**Bluetooth Classic**4、**ESP-NOW**5、Wi-Fi&#xff08;客户端-服务器通信协议&#xff09;6、MQTT7、**LoRa**8、**GSM/GPRS/LTE**9、总结 ESP32是一个基于…

如何使用ArcGIS Pro直接获取道路中心线

以前使用ArcGIS获取道路中心线&#xff0c;需要先将面要素转换为栅格再获取中心线&#xff0c;现在我们可以通过ArcGIS Pro直接获取道路中心线&#xff0c;这里为大家介绍一下获取方法&#xff0c;希望能对你有所帮助。 新建地理数据库 在存储数据的文件夹上点击右键&#xff…

专栏更新情况:华为流程、产品经理、战略管理、IPD

目录 前言 01 华为流程体系入门课 CSDN学院 02 产品经理进阶课 CSDN学院 03 BLM 战略方法论进阶课 04 IPD 进阶 100 例专栏 作者简介 前言 已上线四大课程专栏更新情况&#xff1a; 01 华为流程体系入门课&#xff08;视频图文&#xff09;&#xff1b; 02 硬件产品经…

Linux文件查找,别名,用户组综合练习

1.文件查看: 查看/etc/passwd文件的第5行 [rootserver ~]# head -5 /etc/passwd root:x:0:0:root:/root:/bin/bash bin:x:1:1:bin:/bin:/sbin/nologin daemon:x:2:2:daemon:/sbin:/sbin/nologin adm:x:3:4:adm:/var/adm:/sbin/nologin lp:x:4:7:lp:/var/spool/lpd:/sbin/nologi…

使用YOLOv5的backbone网络识别图像天气 - P9

目录 环境步骤环境设置包引用声明一个全局的设备 数据准备收集数据集信息构建数据集在数据集中读取分类名称划分训练、测试数据集数据集划分批次 模型设计编写维持卷积前后图像大小不变的padding计算函数编写YOLOv5中使用的卷积模块编写YOLOv5中使用的Bottleneck模块编写YOLOv5…

信息安全:网络物理隔离技术原理与应用.

信息安全&#xff1a;网络物理隔离技术原理与应用. 随着网络攻击技术不断增强&#xff0c;恶意入侵内部网络的风险性也相应急剧提高。满足内外网信息及数据交换需求&#xff0c;又能防止网络安全事件出现的安全技术就应运而生了&#xff0c;这种技术称为“物理隔离技术” 基本原…

企业工程项目管理系统源码(三控:进度组织、质量安全、预算资金成本、二平台:招采、设计管理)

工程项目管理软件&#xff08;工程项目管理系统&#xff09;对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营&#xff0c;全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&am…

照片后期处理软件DxO FilmPack 6 mac中文说明

DxO FilmPack 6 for Mac是一款照片后期处理软件。它可以模拟超过60种著名胶片品牌和类型的色彩和颗粒感&#xff0c;使照片具有复古、艺术和时尚风格。 ​DxO FilmPack 6 mac支持RAW和JPG格式的照片&#xff0c;并提供丰富的调整选项&#xff0c;如亮度、对比度、曝光、阴影和高…

web:[极客大挑战 2019]Upload

题目 页面显示为一个上传&#xff0c;猜测上传一句话木马文件 先查看源代码看一下有没有有用的信息&#xff0c;说明要先上传图片&#xff0c;先尝试上传含有一句话木马的图片 构造payload <?php eval($_POST[123]);?> 上传后页面显示为&#xff0c;不能包含<&…

MySQL 索引介绍和最佳实践

目录 一、前言二、索引类型1.1 主键索引&#xff08;PRIMARY KEY&#xff09;1.2 唯一索引&#xff08;UNIQUE&#xff09;1.3 普通索引&#xff08;NORMAL&#xff09;1.3.1 单列普通索引1.3.2 单列前缀普通索引1.3.3 多列普通索引1.3.4 多列前缀普通索引 1.4 空间索引&#x…

微信小程序开发基础(一)认识小程序

微信小程序&#xff0c;小程序的一种&#xff0c;英文名Wechat Mini Program&#xff0c;是一种不需要下载安装即可使用的应用&#xff0c;它实现了应用“触手可及”的梦想&#xff0c;用户扫一扫或搜一下即可打开应用。微信小程序是一种不用下载就能使用的应用&#xff0c;也是…

React(react18)中组件通信06——redux-toolkit + react-redux

React&#xff08;react18&#xff09;中组件通信06——redux-toolkit react-redux 1 前言1.1 redux 和 react-redux1.2 关于redux-toolkit1.2.1 官网1.2.2 为什么要用Redux Toolkit&#xff1f; 1.3 安装 Redux Toolkit1.4 Redux Toolkit相关API 2. 开始例子——官网例子2.1 …

更直观地学习 Git 命令

theme: condensed-night-purple 前言 本文参考于 Learn Git Branching 这个有趣的 Git 学习网站。 在该网站&#xff0c;可以使用 show command 命令展示所有可用命令。 你也可以直接访问网站的sandbox&#xff0c;自由发挥。 本地篇 基础篇 git commit git commit将暂…

文件I/O与标准I/O

如果不知道inode&#xff0c;请看这篇文章inode 我们知道当打开一个文件时&#xff0c;OS会先使用inode编号在磁盘文件系统里面去寻找这个文件&#xff0c;找到以后根据文件的属性为其创建一个内核层面的结构体来描述这个文件&#xff0c;该结构体里面含有文件的属性信息&#…

蓝桥杯 题库 简单 每日十题 day11

01 质数 质数 题目描述 给定一个正整数N&#xff0c;请你输出N以内&#xff08;不包含N&#xff09;的质数以及质数的个数。 输入描述 输入一行&#xff0c;包含一个正整数N。1≤N≤10^3 输出描述 共两行。 第1行包含若干个素数&#xff0c;每两个素数之间用一个空格隔开&…

SpringMVC+统一表现层返回值+异常处理器

一、统一表现层返回值 根据我们不同的处理方法&#xff0c;返回的数据格式都会不同&#xff0c;例如添加只返回true|false&#xff0c;删除同理&#xff0c;而查询却返回数据。 Result类 为此我们封装一个result类来用于表现层的返回。 public class Result {//描述统一格式…