【GESP强化四级】搭档训练 - 题目详情

提交1 通过1

通过率100%

时间限制2000ms

内存限制256MiB

题目描述提交答案

ID: 11239

传统题

2000ms

256MiB

难度: 普及

上传者:

标签>

GESP

GESP强化

C++

c++

编程题

结构体和排序算法

排序

贪心配对

训练班有偶数名学员，第 $i$ 人的编程能力为 $a_i$ 。刘老师要把所有人分成两人一组，每组恰好两人，每名学员也必须恰好进入一个小组。只有能力值相同的两人才可以成为正式搭档。

学员可以通过完成练习题提高能力，每完成一道题，能力值增加 $1$ 。为了让所有人最终都能组成正式搭档，训练系统会计算全体学员最少一共需要完成多少道练习题。

输入格式

第一行输入偶数 $n$ ；第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 。

输出为了让所有人两两组成能力相同的搭档，全体学员最少需要完成的练习题总数。

6
5 10 2 3 14 5

2
1 100

48
79 59 23 58 21 39 37 92 5 84 56 12 99 8 48 9 68 27 88 87 97 21 14 78 83 52 22 19 58 3 38 92 2 38 23 64 29 29 90 38 3 95 21 60 55 4 4 65

排序后能力为 2、3、5、5、10、14。可让能力 2 的学员完成 1 题后与 3 配对，两个 5 直接配对，能力 10 的学员完成 4 题后与 14 配对，总共完成 5 题。