田忌赛马算法：巧用策略求得分差最大值及开发注意要点

```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int n; // 读取马匹数量 cin >> n; vector<int> tianji(n); vector<int> qiwang(n); // 读取田忌的马匹速度 for (int i = 0; i < n; ++i) { cin >> tianji[i]; } // 读取齐王的马匹速度 for (int i = 0; i < n; ++i) { cin >> qiwang[i]; } // 对田忌的马匹速度进行排序 sort(tianji.begin(), tianji.end()); int tianji_score = 0; int qiwang_score = 0; // 双指针，left指向田忌最慢的马，right指向田忌最快的马 int left = 0, right = n - 1; for (int i = 0; i < n; ++i) { if (tianji[right] > qiwang[i]) { // 若田忌最快的马比齐王当前马快，用最快的马比赛并获胜 tianji_score++; right--; } else if (tianji[left] > qiwang[i]) { // 若田忌最快的马不如齐王当前马，但最慢的马比齐王当前马快，用最慢的马比赛并获胜 tianji_score++; left++; } else if (tianji[left] < qiwang[i]) { // 若田忌最慢的马比齐王当前马慢，用最慢的马输掉比赛 qiwang_score++; left++; } // 若速度一样，分数不变，用最慢的马消耗齐王当前马 } // 计算田忌得分减齐王得分的最大值 int result = tianji_score - qiwang_score; cout << result << endl; return 0; } ``` 我在以往的开发过程中，碰到过以下几点需要格外小心处理的地方： 1. 排序操作是必要的，要确保对田忌的马匹速度进行排序，否则无法正确使用贪心策略。 2. 双指针的移动逻辑要清晰，不同情况下指针的移动要正确，避免出现指针越界等错误。 3. 对于速度相等的情况，要按照策略用最慢的马去消耗齐王的马，避免错误的判断。 ######[AI写代码神器 | 567点数解答 | 2025-08-29 11:43:43]