2024年CSP-S决斗问题解析：贪心算法与双指针策略的巧妙应用
一、问题理解与算法选择
题目要求计算n名选手两两决斗后最多能保留多少名选手。核心思路是：当选手A的战斗力小于选手B时，A会被淘汰，我们需要找出最优的匹配策略。
算法选择理由：
二、完整代码实现（带详细注释）
#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;
}三、核心算法解析
排序预处理：
将选手按战斗力升序排列
使得我们可以用贪心策略依次处理
双指针策略：
i指针追踪当前最小战斗力选手
j指针寻找可以淘汰i的选手
淘汰逻辑：
当r[i] < r[j]时完成一次有效淘汰
每次淘汰后两个指针都向前移动
否则只移动j指针寻找更大战斗力的选手
四、复杂度分析与优化
时间复杂度：
排序：O(nlogn)
双指针遍历：O(n)
总体：O(nlogn)
空间复杂度：
使用vector存储：O(n)
哈希表虽然分配但实际未充分利用
潜在优化：
原创内容 转载请注明出处
