当前位置：首页 > news >正文

贪心算法在Karate Competition问题中的应用与优化

news 2026/7/19 1:40:03

1. 题目背景与问题理解

"Karate Competition"是LightOJ平台第1198号题目，属于典型的贪心算法应用场景。题目模拟了一场空手道比赛，我们需要为两支队伍（我方和对方）的选手匹配对战，以最大化我方得分。

比赛规则核心是：

双方各有N名选手
每位选手有确定的实力值
对战匹配遵循"实力相近优先"原则
得分规则：
- 我方选手实力>对方：得2分
- 实力相等：得1分
- 实力不足：得0分

2. 贪心算法选择与证明

2.1 为什么选择贪心算法

这类匹配问题通常有几种解法：

暴力枚举：O(N!)复杂度，完全不可行
动态规划：O(N^2)或更高，实现复杂
贪心算法：O(N logN)排序+O(N)匹配，最优选择

贪心策略的有效性基于：

问题具有最优子结构性质
无后效性：当前选择不影响后续决策
能够通过局部最优达到全局最优

2.2 具体贪心策略

采用双指针法的贪心实现：

将双方选手实力分别排序（升序/降序均可）
初始化两个指针分别指向两个序列的头部
比较当前指针位置的选手实力：
- 我方强：得2分，双方指针都右移
- 实力相等：得1分，双方指针都右移
- 我方弱：得0分，仅我方指针右移

这个策略能确保：

不浪费高实力选手在低价值对战上
实力相近的匹配优先处理
避免低实力选手"阻挡"高实力选手

3. 算法实现细节

3.1 输入处理

LightOJ的典型输入格式：

T (测试用例数) 每个用例： N (选手人数) 我方选手实力列表 对方选手实力列表

示例输入：

1 3 2 1 3 1 2 3

3.2 核心代码实现（C++）

#include <algorithm> #include <vector> using namespace std; int maxScore(vector<int>& our, vector<int>& opp) { sort(our.begin(), our.end()); sort(opp.begin(), opp.end()); int score = 0; int i = 0, j = 0; int n = our.size(); // 第一轮：争取2分 while (i < n && j < n) { if (our[i] > opp[j]) { score += 2; i++; j++; } else { i++; } } // 重置指针，争取1分 i = j = 0; while (i < n && j < n) { if (our[i] == opp[j]) { score += 1; i++; j++; } else if (our[i] < opp[j]) { i++; } else { j++; } } return score; }

3.3 复杂度分析

排序：O(N logN)
两轮匹配：O(N)
总复杂度：O(N logN)

4. 边界条件与测试用例

4.1 必须考虑的边界情况

N=0（空输入）
N=1（最小规模）
所有实力相等
我方全部强于对方
我方全部弱于对方
大规模数据（验证时间复杂度）

4.2 测试用例设计

测试用例1： 2 1 3 2 4 预期输出：2 测试用例2： 3 5 5 5 5 5 5 预期输出：3 测试用例3： 4 1 2 3 4 4 3 2 1 预期输出：6

5. 算法优化与变种

5.1 单次遍历优化

可以合并两次匹配为一次遍历：

int maxScoreOptimized(vector<int>& our, vector<int>& opp) { sort(our.begin(), our.end()); sort(opp.begin(), opp.end()); int score = 0; int low = 0, high = 0; int n = our.size(); // 先匹配能得2分的情况 while (low < n && high < n) { if (our[low] > opp[high]) { score += 2; low++; high++; } else { low++; } } // 剩余选手匹配 low = high = 0; vector<bool> used(n, false); while (low < n && high < n) { if (our[low] == opp[high] && !used[high]) { score += 1; used[high] = true; low++; high++; } else if (our[low] < opp[high]) { low++; } else { high++; } } return score; }