← 返回题目列表

Codeforces · 1532/D

D. 团队组建

中文机器翻译题面 查看原题

一所大学有 $$$n$$$ 名学生。学生人数是偶数。第 $$$i$$$ 学生的编程技能等于 $$$a_i$$$。

教练想要组建 $$$\frac{n}{2}$$$ 团队。每个团队必须由两名学生组成,并且每个学生必须属于一个团队。两个学生只有在技能相当的情况下才能组队(否则他们无法互相理解,无法组队)。

学生可以解决问题来提高他们的技能。解决一个问题,技能就会加一。

教练想知道学生应该解决的最少问题总数才能准确组成 $$$\frac{n}{2}$$$ 团队(即每对学生应组成一个团队)。你的任务是找到这个号码。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 学生人数。保证 $$$n$$$ 是偶数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个学生的技能。

输出

打印一个数字 — 学生为组建 $$$\frac{n}{2}$$$ 团队而应解决的最少问题总数。

示例

输入 #1

6
5 10 2 3 14 5

输出 #1

5

输入 #2

2
1 100

输出 #2

99

注意

在第一个示例中,最佳团队将是:$$$(3, 4)$$$、$$$(1, 6)$$$ 和 $$$(2, 5)$$$,其中括号中的数字是学生的索引。然后,要组成第一队,第三个学生应该解决$$$1$$$问题,要组成第二队,没有人需要解决问题,要组成第三队,第二个学生应该解决$$$4$$$问题,所以答案是$$$1 + 4 = 5$$$。

在第二个示例中,第一个学生应该解决 $$$99$$$ 问题,以便与第二个学生组成一个团队。