1. 题目背景与问题理解

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

比赛规则核心是：

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

2. 贪心算法选择与证明

2.1 为什么选择贪心算法

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

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

贪心策略的有效性基于：

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

2.2 具体贪心策略

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

1. 将双方选手实力分别排序（升序/降序均可）
2. 初始化两个指针分别指向两个序列的头部
3. 比较当前指针位置的选手实力：
   • 我方强：得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 必须考虑的边界情况

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

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; }

5.2 变种问题思考

1. 如果比赛规则改变（如不同分差对应不同得分）？
2. 如果允许选手重复出战？
3. 如果双方选手人数不同？
4. 如果加入选手权重系数？

6. 实际编码中的注意事项

1. 输入输出效率：

   • 使用快速的IO方法（如C++的ios::sync_with_stdio(false)）
   • 避免不必要的输入复制

2. 排序方向：

   • 升序或降序均可，但要保持一致性
   • 推荐升序排序，更符合常规思维

3. 指针移动逻辑：

   • 确保不会数组越界
   • 注意处理相等情况的指针移动

4. 多测试用例处理：

   • 记得清空或重置数据结构
   • 避免前一个用例的数据污染

7. 同类问题推荐

1. LeetCode 870. Advantage Shuffle
2. Codeforces 分饼干问题
3. 区间调度问题（Interval Scheduling）
4. 任务分配问题
5. 背包问题的某些变种

在解决这类匹配问题时，关键在于识别问题的贪心性质并设计合适的匹配策略。实际比赛中，建议先手动模拟小规模案例，验证算法正确性后再编码实现。