首页田忌赛马贪心算法c++

田忌赛马贪心算法c++

时间: 2024-05-12 18:11:51 浏览: 232

田忌赛马问题是一道经典的贪心算法问题。假设田忌和齐王各有若干匹马，他们要进行若干次比赛，每次比赛每人选出一匹马参赛，胜者得一分，平局得半分，败者得零分。现在田忌和齐王都知道对方的马速，他们想要通过巧妙安排马匹的顺序，让自己最终得分最高。贪心策略是，让田忌的最慢的马匹去和齐王的最快的马匹比赛。如果田忌的最慢马匹赢了，那么胜利的几率就更大，否则就换下一匹最慢的马匹。这样一直比下去，直到所有比赛都结束。以下是C++代码实现： ```c++ #include <iostream> #include <algorithm> using namespace std; int main() { int n; int tian[1005], qi[1005]; while (cin >> n && n != 0) { for (int i = 0; i < n; i++) { cin >> tian[i]; } for (int i = 0; i < n; i++) { cin >> qi[i]; } sort(tian, tian + n); sort(qi, qi + n); int t = 0, q = 0, ans = 0; while (t < n && q < n) { if (tian[t] > qi[q]) { ans++; t++; q++; } else if (tian[t] < qi[q]) { ans--; t++; } else { if (tian[n - 1] > qi[n - 1]) { ans++; } t++; q++; } } cout << ans * 200 << endl; } return 0; } ```

阅读全文