1. 项目背景与问题定义
"Karate Competition"是LightOJ平台第1198号编程题目，属于典型的贪心算法应用场景。这道题目模拟了空手道比赛中的选手匹配问题，要求我们找到最优的对抗策略使己方获得最大胜利场次。
在实际比赛中，两支队伍各有N名选手，每位选手都有特定的实力值。比赛规则采用一对一对抗模式，当己方选手实力严格大于对方时得1分，平局或失败不得分。题目核心在于如何通过合理的选手匹配策略，最大化己方的总得分。
2. 算法思路解析
2.1 贪心算法选择依据
这类匹配问题通常有几种经典解法：
- 暴力枚举（O(n!)复杂度，不可行）
- 动态规划（O(n^2)复杂度，可能超时）
- 贪心算法（O(nlogn)复杂度，最优选择）
选择贪心算法主要基于以下考虑：
- 问题具有最优子结构性质
- 局部最优解能导致全局最优解
- 排序预处理后时间复杂度可控
2.2 具体实现策略
经过分析，最有效的贪心策略是：
- 对双方选手实力分别进行升序排序
- 使用双指针法进行匹配：
- 优先用最小优势获胜（节省强选手）
- 无法获胜时用最弱选手消耗对方强手
这种策略在O(nlogn)时间内能确保获得最大可能得分。
3. 代码实现详解
3.1 输入处理与排序
int n; cin >> n; vector<int> our(n), opp(n); for(int i=0; i<n; i++) cin >> our[i]; for(int i=0; i<n; i++) cin >> opp[i]; sort(our.begin(), our.end()); sort(opp.begin(), opp.end());关键点：
- 使用vector容器存储选手数据
- 默认升序排序便于后续处理
- 时间复杂度：O(nlogn)
3.2 双指针匹配算法
int score = 0; int i = 0, j = 0, k = n-1, l = n-1; while(i <= k) { if(our[i] > opp[j]) { score++; i++; j++; } else if(our[k] > opp[l]) { score++; k--; l--; } else { if(our[i] < opp[l]) score--; i++; l--; } }算法说明：
- i/k指向我方当前最小/最大选手
- j/l指向对方当前最小/最大选手
- 三种情况处理：
- 我方最小 > 对方最小：直接得分
- 我方最大 > 对方最大：直接得分
- 否则用我方最小消耗对方最大
3.3 完整解决方案
#include <bits/stdc++.h> using namespace std; int solve() { int n; cin >> n; vector<int> our(n), opp(n); for(int i=0; i<n; i++) cin >> our[i]; for(int i=0; i<n; i++) cin >> opp[i]; sort(our.begin(), our.end()); sort(opp.begin(), opp.end()); int score = 0; int i = 0, j = 0, k = n-1, l = n-1; while(i <= k) { if(our[i] > opp[j]) { score++; i++; j++; } else if(our[k] > opp[l]) { score++; k--; l--; } else { if(our[i] < opp[l]) score--; i++; l--; } } return score * 200; } int main() { int T; cin >> T; for(int t=1; t<=T; t++) { cout << "Case " << t << ": " << solve() << endl; } return 0; }4. 算法正确性证明
4.1 贪心选择性质
该策略的贪心选择性体现在：
- 当存在可以立即得分的匹配时优先取得分数
- 在必须牺牲时选择代价最小的方式（用最弱选手）
4.2 最优子结构
将问题分解为子问题：
- 每次处理一对选手匹配
- 剩余选手构成规模更小的相同性质子问题
- 子问题的最优解能构成原问题最优解
4.3 严格证明
使用数学归纳法：
- 基本情况：n=1时显然成立
- 归纳假设：对n=k成立
- 归纳步骤：
- 若our[0]>opp[0]，匹配这对选手最优
- 否则our[0]必须与某个opp[x]匹配，选择最大的x最优
5. 复杂度分析与优化
5.1 时间复杂度
主要时间消耗：
- 排序：O(nlogn)
- 双指针匹配：O(n)
- 总体：O(nlogn)
5.2 空间复杂度
仅需存储两个数组：
- O(n)空间
5.3 可能的优化
- 输入输出优化：
ios::sync_with_stdio(false); cin.tie(0); - 使用原生数组替代vector（性能提升有限）
- 并行排序（大数据量时）
6. 边界条件与测试用例
6.1 关键边界情况
- 所有选手实力相同
- 我方完全强于/弱于对方
- 单选手情况
- 最大规模数据（n=50）
6.2 测试用例示例
输入：
1 3 2 1 3 1 2 3处理过程：
- 排序后： our: [1,2,3] opp: [1,2,3]
- 匹配：
- our[1]=2 > opp[0]=1 → 得分
- our[2]=3 > opp[1]=2 → 得分
- our[0]=1 == opp[2]=3 → 不得分
- 输出：400
7. 同类问题扩展
7.1 变种问题
- 平局也得0.5分
- 多轮比赛累计得分
- 团队对抗（每组多人）
7.2 相关题目
- UVA 1344 - Tian Ji's Horse Racing
- Codeforces 578B - "Or" Game
- LeetCode 870 - Advantage Shuffle
8. 实际应用场景
该算法思想可应用于：
- 电竞比赛选手匹配
- 工作任务分配优化
- 资源调度策略
- 竞价排名系统
提示：在实现时要注意LightOJ的特殊输出要求（Case编号和得分×200）
我在实际解决这个问题时发现，将双方选手实力可视化绘制成折线图，能更直观地理解匹配策略的有效性。对于n=20左右的中等规模数据，建议在本地生成随机测试用例验证算法正确性。
