2024年CSP-S决斗问题解析：贪心算法与双指针策略的巧妙应用
https://dajuwangluo.cn/zb_users/upload/2025/06/202506081749361936262620.jpg一、问题理解与算法选择题目要求计算n名选手两两决斗后最多能保留多少名选手。核心思路是：当选手A的战斗力小于选手B时，A会被淘汰，我们需要找出最优的匹配策略。算法选择理由：
[*]贪心算法：总希望当前最小的选手能匹配到刚好比它大的对手
[*]双指针技巧：高效遍历已排序数组的最佳选择
[*]时间复杂度：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;
}
// 关键步骤1：排序战斗力
sort(r.begin(), r.end());
// 统计每个战斗力出现的频率（虽然本题未直接使用）
unordered_map<int, int> freq;
for (int num : r) {
freq++;
}
// 初始假设所有选手都会被保留
int res = n;
// 双指针初始化
int i = 0, j = 1;
// 关键步骤2：贪心匹配
while (i < n && j < n) {
if (r < r) {// 找到可以淘汰i的j
res--; // 淘汰i选手
i++; // 处理下一个最小选手
j++; // j也需要移动
} else { // 当前j不足以淘汰i
j++; // 尝试更大的j
}
}
// 输出最终保留的选手数量
cout << res << endl;
return 0;
}
[*]将选手按战斗力升序排列
[*]使得我们可以用贪心策略依次处理
双指针策略：
[*]i指针追踪当前最小战斗力选手
[*]j指针寻找可以淘汰i的选手
淘汰逻辑：
[*]当r < r时完成一次有效淘汰
[*]每次淘汰后两个指针都向前移动
[*]否则只移动j指针寻找更大战斗力的选手
原文：2024年CSP-S决斗问题解析：贪心算法与双指针策略的巧妙应用
页:
[1]