思路：优先队列

统计每个数的个数，然后用一个优先队列维护每个数，按照每个数出现的次数的一个小根堆。

一个贪心想法是，考虑每个数先和其他每个数配对一次，然后剩余多的数再自己和自己匹配。

因为每个数 $n$ 个，每个数至多各进出一次优先队列。

至于为什么需要先和其他数匹配，再和自己匹配。

考虑如下这个例子：[1, 1, 2, 2, 2, 2, 3, 3]

如果考虑优先自己匹配，那么剩下 [2, 2] 无法匹配。

如果优先考虑和其他数匹配，那么匹配的结果就是：

• [1, 2], [1, 3]
• [2, 3], [2, 2]

时间复杂度：$O(n\log n)$

代码

c++

#include <bits/stdc++.h>
using namespace std;
map<int, int> cnt;
vector<int> tmp;
priority_queue<int> q;
int main()
{
	int n;
	cin >> n;
	while(n--) {
		int x;
		cin >> x;
		cnt[x] ++;
	}
	for(auto g: cnt) {
		q.push(g.second);
	}
	int ans = 0;
	while(q.size()) {
		int t = q.top();
		q.pop();
		if(t >= 2) t -= 2, ans ++;
		while(q.size() && t--) {
			tmp.push_back(q.top()-1);
			q.pop();
			ans ++;
		}
		while(tmp.size()) {
			if(tmp.back())
				q.push(tmp.back());
			tmp.pop_back();
		}
	}
	cout << ans << endl;
}

python

n = int(input())
nums = list(map(int, input().split()))

from collections import *
cnt = Counter(nums)
tmp = []
tmp.append(list(cnt.keys()))
tmp.append(list(cnt.values()))
tmp.sort(key = lambda x : -x[1])
keys = tmp[0]
n = len(keys)

res = 0
for i in range(n):
    key1 = keys[i]
    num = cnt[key1]
    j = i + 1
    while num != 0 and j < n:
        key2 = keys[j]
        if cnt[key2] > 0:
            num-=1
            res += 1
            cnt[key2] -= 1
            cnt[key1] -= 1
        j += 1
for key, value in cnt.items():
    if value >= 2:
        res += 1
        cnt[key] = 0
    else:
        cnt[key] = 0

print(res)

java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Map<Integer, Integer> counter = new HashMap<>();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            int num = scan.nextInt();
            nums[i] = num;
            int count = counter.getOrDefault(num, 0) + 1;
            counter.put(num, count);
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return counter.get(o2) - counter.get(o1);
            }
        });
        PriorityQueue<Integer> queue2 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return counter.get(o2) - counter.get(o1);
            }
        });
        for (int j : counter.keySet()) {
            queue.offer(j);
        }
        long res = 0L;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int size = queue.size(), count = counter.get(cur);
            if (size < count) {
                res += size;
                count -= size;
                if (count >= 2) res++;
            } else {
                res += count;
                size = count;
            }

            for (int i = 0; i < size; i++) {
                int num = queue.poll();
                if (counter.get(num) > 1) {
                    counter.put(num, counter.get(num) - 1);
                    queue2.offer(num);
                }
            }
            queue.addAll(queue2);
            queue2.clear();
        }
        System.out.println(res);
    }
}
\

题目描述

小美有 $n$ 个数，现在他想给 $n$ 个数两两配对，假设配对后为 $(a,b), a\leq b$ 。

现在他想问你，最多可以有多少不同的配对组合。

注意，$(a,b)$ 和 $(b,a)$ 视为一种配对组合。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$ 表示数的数量。
第二行， $n$ 个整数，第 $i$ 个为 $a_i(1 \leq a_i \leq 10^9)$ 。

输出描述

一个整数

样例

输入

8
1 1 2 2 2 2 3 3 

输出

4

说明

(1,2) (1,3) (2,3) (2,2)