第十四届蓝桥杯国赛 C++ B 组 C 题——班级活动(AC)

2024-01-26 18:04

本文主要是介绍第十四届蓝桥杯国赛 C++ B 组 C 题——班级活动(AC),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1. 班级活动
    • 1. 问题描述
    • 2. 输入格式
    • 3. 输出格式
    • 4. 样例输入
    • 5. 样例输出
    • 6. 样例说明
    • 7. 评测用例规模与约定
    • 8. 原题链接
  • 2. 解题思路
  • 3. AC_Code

1. 班级活动

前置知识点:思维,分类讨论

1. 问题描述

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

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

2. 输入格式

输入共 2 2 2 行。

第一行为一个正整数 n n n

第二行为 n n n 个由空格隔开的整数 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an

3. 输出格式

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

4. 样例输入

4
1 2 2 3

5. 样例输出

1

6. 样例说明

仅需要把 a 1 a_1 a1 改为 3 3 3 或者把 a 3 a_3 a3 改为 1 1 1 即可。

7. 评测用例规模与约定

对于 20 % 20\% 20% 的数据,保证 n ≤ 1 0 3 n ≤ 10^3 n103

对于 100 % 100\% 100% 的数据,保证 n ≤ 1 0 5 n ≤ 10^5 n105

8. 原题链接

班级活动

2. 解题思路

首先明确一点,假设某个 id \text{id} id 的同学数量为 x ( x > 2 ) x(x>2) x(x>2),因为题目要求任意 id \text{id} id 只能有两名同学,所以一定会有 x − 2 x-2 x2 名同学修改自己的 id \text{id} id。我们可以计算出每个 id \text{id} id 需要修改自身的同学数量之和,并将这个数量设为 b b b,即满足:
b = ∑ i = 1 n max ⁡ ( 0 , a i − 2 ) b=\sum_{i=1}^{n}\max(0,a_i-2) b=i=1nmax(0,ai2)
还有一个特殊群体我们不能忽略,就是编号 id \text{id} id 唯一的同学,我们设这群同学的数量为 a a a。他们特殊在有可能需要修改自身 id \text{id} id,也有可能不需要,我们需要进行分类讨论。

  • b ≥ a b \ge a ba 时:

在这种情况下, id \text{id} id 唯一的 a a a 名同学是不需要修改自身 id \text{id} id 的。我们可以从 b b b 名同学中选出 a a a 名同学修改自身 id \text{id} id 去与 id \text{id} id 唯一的同学对应,剩下的 b − a b-a ba 名同学仍然是需要修改自身 id \text{id} id 的,所以答案即是 b b b

假设有一个 id \text{id} id 集合 A = { 1 , 2 , 3 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5 } A= \lbrace1,2,3,4,4,4,4,5,5,5,5,5\rbrace A={1,2,3,4,4,4,4,5,5,5,5,5},此时 id \text{id} id 唯一的集合为 { 1 , 2 , 3 } \lbrace1,2,3\rbrace {1,2,3},必须修改的 id \text{id} id 集合为 { 4 , 4 , 5 , 5 , 5 } \lbrace4,4,5,5,5\rbrace {4,4,5,5,5}。我们只需要让后一个集合的 id \text{id} id 分别修改为 { 1 , 2 , 3 , 6 , 6 } \lbrace 1,2,3,6,6\rbrace {1,2,3,6,6} 即可符合要求。

  • b < a b<a b<a 时:

在这种情况下,部分 id \text{id} id 唯一的 a a a 名同学是需要修改自身 id \text{id} id 的。同样假设有一个 id \text{id} id 集合 A = { 1 , 2 , 3 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 6 , 7 } A=\lbrace1,2,3,4,5,5,5,5,5,5,6,7\rbrace A={1,2,3,4,5,5,5,5,5,5,6,7},此时 id \text{id} id 唯一的集合为 { 1 , 2 , 3 , 4 , 6 , 7 } \lbrace1,2,3,4,6,7\rbrace {1,2,3,4,6,7},必须修改的 id \text{id} id 集合为 { 5 , 5 , 5 , 5 } \lbrace5,5,5,5\rbrace {5,5,5,5}。按照同样策略,我们让必须修改的 id \text{id} id 集合与 id \text{id} id 唯一的集合对应上,即将必须修改的 id \text{id} id 集合变为 { 1 , 2 , 3 , 4 } \lbrace1,2,3,4\rbrace {1,2,3,4}

但此时仍然发现 id \text{id} id 唯一的集合剩余的两个 id \text{id} id { 6 , 7 } \lbrace6,7\rbrace {6,7},我们需要让他们它们一致,所以需要修改其中一个。

假设剩余 4 4 4 个呢?那我们需要修改 2 2 2 个。

假设剩余 8 8 8 个呢?那我们需要修改 4 4 4 个。

显然结论就是需要修改剩余 id \text{id} id 个数的一半,即这种情况下答案是:
a − b 2 + b \dfrac{a-b}{2}+b 2ab+b
小疑问:如果 a-b 为奇数怎么办?

结论: a − b a-b ab 一定为偶数。我们可以假设数组已经存在 c c c 对匹配好的 id \text{id} id,根据我们对 a , b a,b a,b 的定义,显然符合式子 a + b + 2 × c = n a+b+2\times c=n a+b+2×c=n。题目告知我们 n n n 一定为偶数,且 2 × c 2 \times c 2×c 也一定为偶数,那么 a + b a+b a+b 也一定为偶数,即说明 a , b a,b a,b 奇偶性一定相同,得证 a − b a-b ab 一定为偶数。

时间复杂度: O ( n ) O(n) O(n)

3. AC_Code

  • C++
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int n;
int main()
{cin >> n;map<int, int> cnt;for (int i = 0; i < n; ++i){int x;cin >> x;cnt[x]++;}int a = 0, b = 0;for (auto [x, y] : cnt){if (y == 1){a++;}else if (y > 2){b += y - 2;}}if (b >= a){cout << b << '\n';}else{cout << (a - b) / 2 + b << '\n';}return 0;
}
  • Java
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();Map<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < n; ++i) {int x = sc.nextInt();cnt.put(x, cnt.getOrDefault(x, 0) + 1);}int a = 0, b = 0;for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {int y = entry.getValue();if (y == 1) {a++;} else if (y > 2) {b += y - 2;}}if (b >= a) {System.out.println(b);} else {System.out.println((a - b) / 2 + b);}}
}
  • Python
n = int(input())
line = list(map(int, input().split()))
cnt = {}
for i in range(n):x = line[i]if x in cnt:cnt[x] += 1else:cnt[x] = 1
a = 0
b = 0
for y in cnt.values():if y == 1:a += 1elif y > 2:b += y - 2
if b >= a:print(b)
else:print((a - b) // 2 + b)

这篇关于第十四届蓝桥杯国赛 C++ B 组 C 题——班级活动(AC)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/647617

相关文章

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快