4248 - 学生分组

题目描述

学校里有 n 个学生,其中 n一定是偶数。每个学生有一定的编程能力,第 i 个学生的能力是 a_i

学校里的老师希望把学生组成 n/2 个队伍,每个队伍里面有 2 个学生,每个学生只能属于一个队伍。两个学生可以组队,当且仅当他们的能力是相同的,否则他们就不能理解对方。

由于开始的时候,学生的能力参差不齐,可能无法顺利组队。但是学生可以通过做题来提高自己的能力,每做一题,能力就可以提高 1

学校的老师希望计算出这些学生最少需要做多少题,才能顺利的组队。

输入

输入的第一行是一个正整数 n,表示学生的数量,保证 n一定是偶数。

接下来一行有 n 个正整数,第 i 个整数 a_i 表示第 i 个学生当前的编程能力。

输出

输出只有一行一个整数,表示所有学生最少需要做的总题数,才能使得顺利组队。

样例

输入

6
5 10 2 3 14 5

输出

5

输入

2
1 100

输出

99
说明

【样例说明】

在第一个样例中,第 3 个人和第 4 个人组队,第 1 个人和第 6 个人组队,第 2 个人和第 5 个人组队,然后第 3 个人做 1 题,第 2 个人做 4 题,总共做 5题,他们就能顺利组队了。

在第二个样例中,由于只有 2 个人,所以组队方案只有 1 种,第 1 个人需要做 99 题才能组队。

【数据范围】

对于 50% 的数据,( 1 \leq n \leq 1000 ),所有学生的能力最多只有2种不同的取值。

对于 100% 的数据,( 1 \leq n \leq 100000 )( 1 \leq a_i \leq 100 )

来源

婺城区第二届青少年信息素养大赛初中组试题

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 37
通过人数 33
金币数量 1 枚
难度 入门


上一题 下一题