题目理解

我们有一个长度为 $n$ 的数组 $a$，初始分数为 $0$。每次操作可以选择两个之前都没被选过的下标 $i$ 和 $j$（$i < j$），且满足 $a_i = a_j$，然后分数加 $1$。问最多能获得多少分。

---

关键观察

$1$. 元素独立配对
由于每次操作选择两个下标，且要求它们对应的数值相等，不同数值之间的操作不会互相影响。因此，我们可以分别考虑每个数值 $x$。

$2$. 频率计数
设 $f_x$ 表示数值 $x$ 在数组 $a$ 中出现的次数。
每次选择两个相等的数值 $x$，就会消耗掉两个值为 $x$ 的元素。
因此，对于数值 $x$，最多能进行的操作次数是 $\left\lfloor \frac{f_x}{2} \right\rfloor$（即两两配对后剩余不足一对的无法使用）。

$3$. 总分数
总分数就是所有不同数值 $x$ 能配对的次数之和：

$$\text{ans} = \sum_{x} \left\lfloor \frac{f_x}{2} \right\rfloor $$

其中 $x$ 的取值范围是数组中出现过的所有数值。

---

算法步骤

$1$. 读入测试数据组数 $t$。 $2$. 对每组测试数据：

• 读入 $n$ 和数组 $a$。
• 因为题目保证 $1 \le a_i \le n$，所以可以开一个长度为 $n+1$ 的计数数组 $cnt$，用于统计每个数值的出现次数。
• 遍历数组 $a$，对于每个 $a_i$，执行 $cnt[a[i]]++$。
• 遍历 $x$ 从 $1$ 到 $n$，将 $cnt[x] / 2$ 累加到答案中。
• 输出答案。

---

时间复杂度

• 每组数据遍历数组一次统计频率：$O(n)$。
• 遍历数值范围计算答案：$O(n)$。
• 总复杂度 $O(t \cdot n)$，在 $t \le 500$，$n \le 20$ 的条件下完全可行。

---

示例验证

以输入：

4
1 2 3 1

为例：

• 数值 $1$ 出现 $2$ 次 → $\lfloor 2/2 \rfloor = 1$
• 数值 $2$ 出现 $1$ 次 → $\lfloor 1/2 \rfloor = 0$
• 数值 $3$ 出现 $1$ 次 → $\lfloor 1/2 \rfloor = 0$
• 答案 = $1 + 0 + 0 = 1$，与题目输出一致。

---

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> cnt(n + 1, 0); // 统计每个数值出现的次数，范围 1..n
        
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            cnt[a[i]]++;
        }
        
        int ans = 0;
        for (int x = 1; x <= n; x++) {
            ans += cnt[x] / 2; // 每对相同的数贡献 1 分
        }
        
        cout << ans << endl;
    }
    return 0;
}