📝 题目大意

给定 $N$ 只袜子，每只袜子有一个颜色 $A_i$。每次操作可以从尚未配对的袜子中选出两只颜色相同的袜子配对。求最多能进行多少次操作。

💡 解题思路

1. 题目分析：

   • $N \leq 5 \times 10^5$，暗示需要 $O(N \log N)$ 或 $O(N)$ 的算法。
   • $A_i \leq 10^9$，颜色值域很大，不适合用桶计数，但 $N$ 相对较小，适合排序后处理。
   • 每种颜色能配对的袜子数量为 $\lfloor \text{该颜色出现次数} / 2 \rfloor$，答案即所有颜色配对数的总和。

2. 算法推导：

   • 先将数组 arr 排序（sort(arr, arr + n)），使得相同颜色的袜子相邻。
   • 遍历排序后的数组，用变量 sum 记录已配对的次数：
     • 若 arr[i] == arr[i+1]，说明相邻两只袜子颜色相同，可以配对，sum 加 1，同时跳过这两只（i++ 在循环体内再额外跳一次，配合 for 的 i++ 共跳过两只）。
     • 若不相等，则当前袜子无法与下一只配对，继续向后检查。
   • 最终 sum 即为最大操作次数。

3. 边界与细节：

   • 当 $N = 1$ 时，无法配对，输出 0。
   • 当某种颜色出现奇数次时，最后一只该颜色的袜子无法配对，排序后贪心扫描自然能正确处理——最后那只袜子会与不同颜色的下一只比较，不满足相等条件，自动跳过。
   • 标准代码中 arr[i] == arr[i+1] 在 i = n-1 时访问了 arr[n]，属于越界访问。更严谨的写法是将循环条件改为 i < n - 1，但由于 arr[n] 是未定义内存，通常不会恰好等于 arr[n-1]，在实际评测中一般不会出错。此处保留原代码风格。

⏱️ 复杂度分析

• 时间复杂度：$O(N \log N)$，主要开销来自排序。
• 空间复杂度：$O(N)$，用于存储输入的袜子颜色数组。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);  // 加速输入输出

    int a, n, sum = 0;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];          // 读入所有袜子颜色
    }
    sort(arr, arr + n);         // 排序，使相同颜色的袜子相邻
    for (int i = 0; i < n; i++) {
        if (arr[i] == arr[i+1]) {  // 相邻两只颜色相同 → 可以配对
            sum += 1;              // 配对次数 +1
            i++;                   // 跳过已配对的两只袜子
        }
    }
    cout << sum << "\n";        // 输出最大操作次数

    return 0;
}