贪心不会了，求思路谢了

Question

最近有些赛马比赛，HEIHEI去当了裁判，比赛规定输的一方要把自己的马匹都给最后胜利者的一方，还有一个特殊的规定就是如果双方的赢的局数一样打成了平局，则裁判赢，双方把马匹都给裁判。比赛规则为双方马匹的能力值大的一方赢这一局,赢的总局数多的一方是最后的胜利者。保证每匹马的能力值都不相同。HEIHEI比较贪心，想安排一下双方马匹的出场顺序以便自己赢得所有马匹，但是HEIHEI不太聪明，不知道怎么安排，现在就请你写一个程序来帮助贪心的HEIHEI吧。

输入
输入有多组测试数据。 输入第一行有一个整数n表示有n匹马（1<=n<=100）。 第二行表示其中一方n马匹的能力值。 第三行表示另外一方n匹马的能力值。

输出
如果贪心的HEIHEI可以赢得所有的马匹就输出“YES”，否则输出“NO”。

样例输入
4
1 2 7 8
3 4 5 6
2
1 2
3 4
样例输出
YES
NO

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

---

贪心算法可以用来解决这个问题。一种可能的思路是，对于每一轮比赛，HEIHEI选择自己能力值最低的马匹与对方能力值最高的马匹进行比赛。这样做可以最大限度地增加自己赢得的局数，并确保自己最终能赢得所有的马匹。

以下是一个用C++实现的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canWinAllHorses(vector<int>& myHorses, vector<int>& opponentHorses) {
    sort(myHorses.begin(), myHorses.end()); // 将自己的马匹按能力值从低到高排序
    sort(opponentHorses.begin(), opponentHorses.end()); // 将对方的马匹按能力值从低到高排序
    
    int n = myHorses.size();
    int myWins = 0; // 记录自己赢得的局数
    
    for (int i = 0; i < n; i++) {
        if (myHorses[i] < opponentHorses[n - i - 1]) { // 如果自己的马匹能力值比对方的高，则赢得这一局
            myWins++;
        } else {
            return false; // 如果无法赢得这一局，则无法赢得所有马匹，返回false
        }
    }
    
    return true; // 如果赢得了所有局数，则可以赢得所有马匹，返回true
}

int main() {
    int n;
    while (cin >> n) {
        vector<int> myHorses(n);
        vector<int> opponentHorses(n);
        for (int i = 0; i < n; i++) {
            cin >> myHorses[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> opponentHorses[i];
        }
        
        if (canWinAllHorses(myHorses, opponentHorses)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

这个示例代码中，canWinAllHorses函数用于判断是否可以赢得所有的马匹。它先将马匹按能力值排序，然后依次比较自己的马匹和对方的马匹，如果自己的马匹能力值比对方的高，就赢得这一局。如果无法赢得某一局，则说明无法赢得所有马匹。

注意，上述代码只提供了一种解决思路，可能还有其他方法可以解决这个问题。