You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
小美有 n 个数,现在他想给 n 个数两两配对,假设配对后为 (a,b),a≤b 。
现在他想问你,最多可以有多少不同的配对组合。
注意,(a,b) 和 (b,a) 视为一种配对组合。
第一行,一个整数 n(1≤n≤105) 表示数的数量。
第二行, n 个整数,第 i 个为 ai(1≤ai≤109) 。
一个整数
输入
8
1 1 2 2 2 2 3 3
输出
4
说明
(1,2) (1,3) (2,3) (2,2)
统计每个数的个数,然后用一个优先队列维护每个数,按照每个数出现的次数的一个小根堆。
一个贪心想法是,考虑每个数先和其他每个数配对一次,然后剩余多的数再自己和自己匹配。
因为每个数 n 个,每个数至多各进出一次优先队列。
至于为什么需要先和其他数匹配,再和自己匹配。