贪心算法：
1、 电池寿命 http://bailian.openjudge.cn/practice/3468
2、 建立雷达 http://bailian.openjudge.cn/practice/1328
3、 田忌赛马 http://bailian.openjudge.cn/practice/2287
“田忌赛马（Tian Ji — The Horse Racing）” 最优贪心算法 + 完整 C++ 代码。
这个问题是典型的：
双指针 + 排序 + 贪心策略
🧠 题解思路（核心贪心策略）
田忌想最大化自己的收益（每赢一局 +200，每输一局 −200）。
将两人马匹速度都排序（从大到小）：
令
t[i]= 田忌的马（降序）k[j]= 国王的马（降序）
用三个指针：
| 指针 | 含义 |
|---|---|
tl |
田忌最慢马的左指针（开始处） |
tr |
田忌最快马的右指针（末尾） |
kl |
国王最慢马 |
kr |
国王最快马 |
贪心策略（最优策略）
对每一轮比较：
1. 如果田忌最快马 > 国王最快马
→ 直接赢！
⚡ tr--, kr--
收益 +200
2. 如果田忌最慢马 > 国王最慢马
→ 让慢马赢慢马
⚡ tl++, kl++
收益 +200
3. 否则田忌当前最慢马 < 国王最快马
→ 只能牺牲最慢马
⚡ tl++, kr--
收益 -200
该策略即官方题解的最优策略，在所有情况下都能保证最大收益。
✅ 完整 C++ 代码
#include <bits/stdc++.h>
using namespace std;int main() { int n;while (cin >> n && n) {vector<int> t(n), k(n);for (int i = 0; i < n; i++) cin >> t[i];for (int i = 0; i < n; i++) cin >> k[i];sort(t.begin(), t.end(), greater<int>());sort(k.begin(), k.end(), greater<int>());int tl = 0, tr = n - 1;int kl = 0, kr = n - 1;int score = 0;while (tl <= tr) {if (t[tl] > k[kl]) {// 田忌最快 > 国王最快 → 赢score += 200;tl++;kl++;} else if (t[tr] > k[kr]) {// 田忌最慢 > 国王最慢 → 也赢score += 200;tr--;kr--;} else {// 不管怎样都赢不了 → 牺牲最慢马if (t[tr] < k[kl])score -= 200; // 输tr--;kl++;}}cout << score << "\n";}return 0;
}
📌 样例测试
输入：
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
输出：
200
0
0