2024年CSP-S决斗问题解析：贪心算法与双指针策略的巧妙应用

一、问题理解与算法选择

题目要求计算n名选手两两决斗后最多能保留多少名选手。核心思路是：当选手A的战斗力小于选手B时，A会被淘汰，我们需要找出最优的匹配策略。

算法选择理由：

1. 贪心算法：总希望当前最小的选手能匹配到刚好比它大的对手

2. 双指针技巧：高效遍历已排序数组的最佳选择

3. 时间复杂度：O(nlogn) 主要来自排序操作

二、完整代码实现（带详细注释）

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

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取选手数量
    int n;
    cin >> n;
    
    // 存储选手战斗力
    vector<int> r(n);
    for (int i = 0; i < n; ++i) {
        cin >> r[i];
    }
    
    // 关键步骤1：排序战斗力
    sort(r.begin(), r.end());
    
    // 统计每个战斗力出现的频率（虽然本题未直接使用）
    unordered_map<int, int> freq;
    for (int num : r) {
        freq[num]++;
    }
    
    // 初始假设所有选手都会被保留
    int res = n;
    
    // 双指针初始化
    int i = 0, j = 1;
    
    // 关键步骤2：贪心匹配
    while (i < n && j < n) {
        if (r[i] < r[j]) {  // 找到可以淘汰i的j
            res--;          // 淘汰i选手
            i++;            // 处理下一个最小选手
            j++;            // j也需要移动
        } else {            // 当前j不足以淘汰i
            j++;            // 尝试更大的j
        }
    }
    
    // 输出最终保留的选手数量
    cout << res << endl;
    
    return 0;
}

三、核心算法解析

1. 排序预处理：

• 将选手按战斗力升序排列

• 使得我们可以用贪心策略依次处理

2. 双指针策略：

• i指针追踪当前最小战斗力选手

• j指针寻找可以淘汰i的选手

3. 淘汰逻辑：

• 当r[i] < r[j]时完成一次有效淘汰

• 每次淘汰后两个指针都向前移动

• 否则只移动j指针寻找更大战斗力的选手

四、复杂度分析与优化

1. 时间复杂度：

• 排序：O(nlogn)

• 双指针遍历：O(n)

• 总体：O(nlogn)

2. 空间复杂度：

• 使用vector存储：O(n)

• 哈希表虽然分配但实际未充分利用

3. 潜在优化：

• 可移除频率统计部分简化代码

• 对于大数据量可使用更快的排序算法