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

约定不等于承诺〃 2024-04-20 11:42 0阅读 0赞

#### 目录 ####

*  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. 样例输出 ###

### 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 n≤103。

对于  100 % 100\\% 100% 的数据，保证  n ≤ 1 0 5 n ≤ 10^5 n≤105。

### 8. 原题链接 ###

[班级活动][Link 1]

## 2. 解题思路 ##

首先明确一点，假设某个  id \\text\{id\} id 的同学数量为  x ( x > 2 ) x(x>2) x(x>2)，因为题目要求任意  id \\text\{id\} id 只能有两名同学，所以一定会有  x − 2 x-2 x−2 名同学修改自己的  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=1∑nmax(0,ai−2)  
还有一个特殊群体我们不能忽略，就是编号  id \\text\{id\} id 唯一的同学，我们设这群同学的数量为  a a a。他们特殊在有可能需要修改自身  id \\text\{id\} id，也有可能不需要，我们需要进行分类讨论。

*  当  b ≥ a b \\ge a b≥a 时：

在这种情况下， 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 b−a 名同学仍然是需要修改自身  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 2a−b\+b  
**小疑问：如果 a-b 为奇数怎么办？**

结论： a − b a-b a−b 一定为偶数。我们可以假设数组已经存在  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 a−b 一定为偶数。

时间复杂度： 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] += 1
        else:
            cnt[x] = 1
    a = 0
    b = 0
    for y in cnt.values():
        if y == 1:
            a += 1
        elif y > 2:
            b += y - 2
    if b >= a:
        print(b)
    else:
        print((a - b) // 2 + b)

[Link 1]: https://www.lanqiao.cn/problems/6218/learning/?page=1&first_category_id=1&sort=students_count&name=%E7%8F%AD%E7%BA%A7%E6%B4%BB%E5%8A%A8