题解 | #田忌赛马#

题目链接

题目描述

田忌与齐威王正在赛马，比赛一共三局，三局两胜，当一方马匹速度严格大于另一方时获胜，每匹马只能出场一次。现在你已经知道了齐威王的马匹上场的顺序，将在第一、二、三场上场的马匹速度分别为 $q_1, q_2, q_3$ 。同时，你也已经知道了田忌所拥有的马匹速度，分别为 $t_1, t_2, t_3$ 。你可以调整田忌的马匹出场顺序，你能否帮助田忌赢得这场比赛？

输入:

第一行输入三个整数 $q_1, q_2, q_3$ 代表齐威王按上场顺序的马匹速度。
第二行输入三个整数 $t_1, t_2, t_3$ 代表田忌拥有的马匹速度。

输出:

如果田忌可以获胜（赢得至少两局），直接输出 Yes，否则输出 No。

解题思路

这是一个经典的博弈问题，但由于马匹数量很少（只有三匹），问题可以被大大简化。我们可以通过枚举所有可能性来暴力求解。

齐威王马匹的出场顺序是固定的，我们用一个数组 $q$ 来存储。田忌的马匹速度则用数组 $t$ 存储。田忌的目标是赢得至少两局比赛。由于他可以任意安排自己的三匹马的出场顺序，总共有 $3! = 6$ 种不同的排列方式。

我们的策略是：

遍历田忌马匹的所有 6 种出场排列。
对于每一种排列，我们将其与齐威王固定的出场顺序进行逐一比较，计算田忌能赢得的局数。胜利的条件是田忌的马速严格大于齐威王的马速。
如果在任何一种排列下，田忌的胜场数大于或等于 2，那么他就存在一种可行的策略来赢得比赛。我们直接输出 Yes 并结束程序。
如果遍历完所有 6 种排列后，都未能找到一个能赢至少两局的方案，那说明田忌不可能获胜，我们输出 No。

这种方法虽然是暴力枚举，但因为问题规模极小，所以非常直接且高效。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    vector<int> q(3);
    vector<int> t(3);
    for (int i = 0; i < 3; ++i) cin >> q[i];
    for (int i = 0; i < 3; ++i) cin >> t[i];

    sort(t.begin(), t.end());

    bool canWin = false;
    do {
        int wins = 0;
        if (t[0] > q[0]) wins++;
        if (t[1] > q[1]) wins++;
        if (t[2] > q[2]) wins++;
        
        if (wins >= 2) {
            canWin = true;
            break;
        }
    } while (next_permutation(t.begin(), t.end()));

    if (canWin) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] q = new int[3];
        ArrayList<Integer> t = new ArrayList<>();
        
        for (int i = 0; i < 3; i++) q[i] = sc.nextInt();
        for (int i = 0; i < 3; i++) t.add(sc.nextInt());
        
        Collections.sort(t);
        
        boolean canWin = false;
        // Manual permutation for 3 elements
        int[][] perms = {
            {t.get(0), t.get(1), t.get(2)},
            {t.get(0), t.get(2), t.get(1)},
            {t.get(1), t.get(0), t.get(2)},
            {t.get(1), t.get(2), t.get(0)},
            {t.get(2), t.get(0), t.get(1)},
            {t.get(2), t.get(1), t.get(0)}
        };

        for (int[] p : perms) {
            int wins = 0;
            if (p[0] > q[0]) wins++;
            if (p[1] > q[1]) wins++;
            if (p[2] > q[2]) wins++;
            
            if (wins >= 2) {
                canWin = true;
                break;
            }
        }
        
        if (canWin) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

import itertools

q = list(map(int, input().split()))
t = list(map(int, input().split()))

can_win = False
for p in itertools.permutations(t):
    wins = 0
    if p[0] > q[0]:
        wins += 1
    if p[1] > q[1]:
        wins += 1
    if p[2] > q[2]:
        wins += 1
    
    if wins >= 2:
        can_win = True
        break

if can_win:
    print("Yes")
else:
    print("No")

算法及复杂度

算法：暴力枚举（全排列）
时间复杂度： $\mathcal{O}(1)$ 。因为马的数量是固定的 3，所以排列数也是固定的 $3! = 6$ 。输入和比较的次数都是常数。
空间复杂度： $\mathcal{O}(1)$ 。我们只需要几个数组来存储马匹的速度。