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 33.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 预期输出：65. 算法优化与变种
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; }5.2 变种问题思考
- 如果比赛规则改变（如不同分差对应不同得分）？
- 如果允许选手重复出战？
- 如果双方选手人数不同？
- 如果加入选手权重系数？
6. 实际编码中的注意事项
输入输出效率：
- 使用快速的IO方法（如C++的ios::sync_with_stdio(false)）
- 避免不必要的输入复制
排序方向：
- 升序或降序均可，但要保持一致性
- 推荐升序排序，更符合常规思维
指针移动逻辑：
- 确保不会数组越界
- 注意处理相等情况的指针移动
多测试用例处理：
- 记得清空或重置数据结构
- 避免前一个用例的数据污染
7. 同类问题推荐
- LeetCode 870. Advantage Shuffle
- Codeforces 分饼干问题
- 区间调度问题（Interval Scheduling）
- 任务分配问题
- 背包问题的某些变种
在解决这类匹配问题时，关键在于识别问题的贪心性质并设计合适的匹配策略。实际比赛中，建议先手动模拟小规模案例，验证算法正确性后再编码实现。