2024年CSP-S决斗题（P11231）解题代码分析与优化指南——洛谷竞赛算法实践

一、题目解读

    2024年CSP-S中的“决斗”题目（洛谷P11231）要求解决一个数组元素对决的问题：给定一个整数数组，每次对决中，相邻元素若数值不同则双方同时被淘汰，相同则保留。最终求剩余的元素数量。题目强调高效算法设计，考验对数据结构和算法逻辑的优化能力。

二、解题思路

采用“排序+双指针+频率统计”策略：

    1. 排序预处理：对原数组升序排序，使相同元素相邻，减少后续比较复杂度。

    2. 频率统计：利用哈希表（unordered_map）统计每个元素的出现次数，避免重复计算。

    3. 双指针优化：通过i、j双指针遍历排序后数组，若r[i] < r[j]，则i、j同时右移（代表淘汰）；若相等，仅j右移（保留重复元素）。最终剩余元素数即为原长度减去淘汰次数。

三、解题步骤

1. 输入与预处理：读入n个元素存入r[]，调用sort()排序。

2. 频率统计：遍历r[]，用freq[]记录每个元素的出现次数。

3. 双指针对决：

    若r[i] < r[j]，说明i与j元素不同，淘汰双方，i、j均后移；

    若r[i] == r[j]，元素相同，仅j后移（保留重复组）。

    循环直至i或j越界，剩余元素数res = n - 淘汰次数。

4. 输出结果：cout输出res。

四、代码与注释

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

int main() {
    ios::sync_with_stdio(false); // 关闭同步加速IO
    cin.tie(nullptr);           // 解除cin与cout绑定

    int n;
    cin >> n;                  // 输入数组长度
    vector<int> r(n);
    for (int i = 0; i < n; ++i) {
        cin >> r[i];           // 读入元素
    }

    sort(r.begin(), r.end());   // 升序排序

    unordered_map<int, int> freq;
    for (int num : r) {         // 统计频率
        freq[num]++;
    }

    int res = n;               // 初始剩余元素数为n
    int i = 0, j = 1;          // 双指针初始化

    while (i < n && j < n) {    // 对决循环
        if (r[i] < r[j]) {      // 元素不同，双方淘汰
            res--;
            i++;
            j++;
        } else {               // 元素相同，保留
            j++;
        }
    }

    cout << res << endl;       // 输出结果
    return 0;
}

五、总结

本解法通过排序+双指针将时间复杂度优化至O(nlogn)，结合哈希表统计频率降低重复判断。核心在于利用排序后“相同元素连续”的性质，双指针高效处理对决逻辑。该思路适用于需处理重复元素的区间问题，是竞赛中常见的优化策略。建议进一步探索其他数据结构（如二分查找）是否可缩短时间复杂度。