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

19339201706

一、问题理解与算法选择

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

算法选择理由：

• 贪心算法：总希望当前最小的选手能匹配到刚好比它大的对手
• 双指针技巧：高效遍历已排序数组的最佳选择
• 时间复杂度：O(nlogn) 主要来自排序操作
  
  

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <unordered_map>
   
5. using namespace std;
   
6. 
   
7. int main() {
   
8.     // 优化输入输出
   
9.     ios::sync_with_stdio(false);
   
10.     cin.tie(nullptr);
    
11.    
    
12.     // 读取选手数量
    
13.     int n;
    
14.     cin >> n;
    
15.    
    
16.     // 存储选手战斗力
    
17.     vector<int> r(n);
    
18.     for (int i = 0; i < n; ++i) {
    
19.         cin >> r[i];
    
20.     }
    
21.    
    
22.     // 关键步骤1：排序战斗力
    
23.     sort(r.begin(), r.end());
    
24.    
    
25.     // 统计每个战斗力出现的频率（虽然本题未直接使用）
    
26.     unordered_map<int, int> freq;
    
27.     for (int num : r) {
    
28.         freq[num]++;
    
29.     }
    
30.    
    
31.     // 初始假设所有选手都会被保留
    
32.     int res = n;
    
33.    
    
34.     // 双指针初始化
    
35.     int i = 0, j = 1;
    
36.    
    
37.     // 关键步骤2：贪心匹配
    
38.     while (i < n && j < n) {
    
39.         if (r[i] < r[j]) {  // 找到可以淘汰i的j
    
40.             res--;          // 淘汰i选手
    
41.             i++;            // 处理下一个最小选手
    
42.             j++;            // j也需要移动
    
43.         } else {            // 当前j不足以淘汰i
    
44.             j++;            // 尝试更大的j
    
45.         }
    
46.     }
    
47.    
    
48.     // 输出最终保留的选手数量
    
49.     cout << res << endl;
    
50.    
    
51.     return 0;
    
52. }

复制代码

• 将选手按战斗力升序排列
• 使得我们可以用贪心策略依次处理
  
  

双指针策略：

• i指针追踪当前最小战斗力选手
• j指针寻找可以淘汰i的选手
  
  

淘汰逻辑：

• 当r < r[j]时完成一次有效淘汰
• 每次淘汰后两个指针都向前移动
• 否则只移动j指针寻找更大战斗力的选手
  
  

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