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

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

1. 班级活动

前置知识点：思维，分类讨论

1. 问题描述

小明的老师准备组织一次班级活动。班上一共有

$n$ 名 (

$n$ 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个

$n$ 以内的正整数作为

text{id}

$id$ ，第

$i$ 名同学的

text{id}

$id$ 为

a_i

$a_{i}$ 。

老师希望通过更改若干名同学的

text{id}

$id$ 使得对于任意一名同学

$i$ ，有且仅有另一名同学

$j$ 的

text{id}

$id$ 与其相同 (

a_i = a_j

$a_{i} = a_{j}$ )。请问老师最少需要更改多少名同学的

text{id}

$id$ ？

2. 输入格式

输入共

$2$ 行。

第一行为一个正整数

$n$ 。

第二行为

$n$ 个由空格隔开的整数

a_1, a_2, …, a_n

$a_{1}, a_{2}, \dots, a_{n}$ 。

3. 输出格式

输出共

$1$ 行，一个整数。

4. 样例输入

4
1 2 2 3

5. 样例输出

6. 样例说明

仅需要把

a_1

$a_{1}$ 改为

$3$ 或者把

a_3

$a_{3}$ 改为

$1$ 即可。

7. 评测用例规模与约定

对于

20%

$20%$ 的数据，保证

≤

n ≤ 10^3

$n \leq 1 0^{3}$ 。

对于

100

100%

$100%$ 的数据，保证

≤

n ≤ 10^5

$n \leq 1 0^{5}$ 。

8. 原题链接

班级活动

2. 解题思路

首先明确一点，假设某个

text{id}

$id$ 的同学数量为

(

)

x(x>2)

$x (x > 2)$ ，因为题目要求任意

text{id}

$id$ 只能有两名同学，所以一定会有

−

x-2

$x - 2$ 名同学修改自己的

text{id}

$id$ 。我们可以计算出每个

text{id}

$id$ 需要修改自身的同学数量之和，并将这个数量设为

$b$ ，即满足：

∑

max

⁡

(

−

)

b=sum_{i=1}^{n}max(0,a_i-2)

$b = i = 1 \sum n max (0, a_{i} - 2)$
还有一个特殊群体我们不能忽略，就是编号

text{id}

$id$ 唯一的同学，我们设这群同学的数量为

$a$ 。他们特殊在有可能需要修改自身

text{id}

$id$ ，也有可能不需要，我们需要进行分类讨论。

在这种情况下，

text{id}

$id$ 唯一的

$a$ 名同学是不需要修改自身

text{id}

$id$ 的。我们可以从

$b$ 名同学中选出

$a$ 名同学修改自身

text{id}

$id$ 去与

text{id}

$id$ 唯一的同学对应，剩下的

−

b-a

$b - a$ 名同学仍然是需要修改自身

text{id}

$id$ 的，所以答案即是

$b$ 。

假设有一个

text{id}

$id$ 集合

{

}

A= lbrace1,2,3,4,4,4,4,5,5,5,5,5rbrace

$A = {1, 2, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}$ ，此时

text{id}

$id$ 唯一的集合为

{

}

lbrace1,2,3rbrace

${1, 2, 3}$ ，必须修改的

text{id}

$id$ 集合为

{

}

lbrace4,4,5,5,5rbrace

${4, 4, 5, 5, 5}$ 。我们只需要让后一个集合的

text{id}

$id$ 分别修改为

{

}

lbrace 1,2,3,6,6rbrace

${1, 2, 3, 6, 6}$ 即可符合要求。

在这种情况下，部分

text{id}

$id$ 唯一的

$a$ 名同学是需要修改自身

text{id}

$id$ 的。同样假设有一个

text{id}

$id$ 集合

{

}

A=lbrace1,2,3,4,5,5,5,5,5,5,6,7rbrace

$A = {1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6, 7}$ ，此时

text{id}

$id$ 唯一的集合为

{

}

lbrace1,2,3,4,6,7rbrace

${1, 2, 3, 4, 6, 7}$ ，必须修改的

text{id}

$id$ 集合为

{

}

lbrace5,5,5,5rbrace

${5, 5, 5, 5}$ 。按照同样策略，我们让必须修改的

text{id}

$id$ 集合与

text{id}

$id$ 唯一的集合对应上，即将必须修改的

text{id}

$id$ 集合变为

{

}

lbrace1,2,3,4rbrace

${1, 2, 3, 4}$ 。

但此时仍然发现

text{id}

$id$ 唯一的集合剩余的两个

text{id}

$id$ 为

{

}

lbrace6,7rbrace

${6, 7}$ ，我们需要让他们它们一致，所以需要修改其中一个。

假设剩余

$4$ 个呢？那我们需要修改

$2$ 个。

假设剩余

$8$ 个呢？那我们需要修改

$4$ 个。

显然结论就是需要修改剩余

text{id}

$id$ 个数的一半，即这种情况下答案是：

−

dfrac{a-b}{2}+b

$\frac{a - b}{2} + b$
小疑问：如果 a-b 为奇数怎么办？

结论：

−

a-b

$a - b$ 一定为偶数。我们可以假设数组已经存在

$c$ 对匹配好的

text{id}

$id$ ，根据我们对

a,b

$a, b$ 的定义，显然符合式子

a+b+2times c=n

$a + b + 2 \times c = n$ 。题目告知我们

$n$ 一定为偶数，且

2 times c

$2 \times c$ 也一定为偶数，那么

a+b

$a + b$ 也一定为偶数，即说明

a,b

$a, b$ 奇偶性一定相同，得证

−

a-b

$a - b$ 一定为偶数。

时间复杂度：

(

)

O(n)

$O (n)$ 。

3. AC_Code

#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)