题解 | #田忌赛马#

题目链接

田忌赛马

题目描述

田忌与齐威王赛马，共三局，三局两胜者赢。田忌的马速度若严格大于齐威王的马，则田忌胜一局。每匹马只能出场一次。

已知齐威王三局比赛的出场马匹速度分别为 $q_1, q_2, q_3$ ，田忌拥有的三匹马速度为 $t_1, t_2, t_3$ 。田忌可以任意安排自己的马匹出场顺序。请判断田忌能否赢得比赛。

解题思路

这是一个典型的决策问题。由于比赛只有三局，田忌的马匹出场顺序组合是有限的。具体来说，有 $3! = 3 \cdot 2 \cdot 1 = 6$ 种不同的出场顺序。

我们可以采用穷举法，即检查田忌所有可能的出场策略。对于每一种策略，我们计算田忌能赢得的局数。只要存在任何一种策略能让田忌赢得至少两局，那么田忌就能赢得整场比赛。

田忌的三匹马速度为 $t_1, t_2, t_3$ ，齐威王的马匹出场顺序固定为 $q_1, q_2, q_3$ 。我们可以遍历田忌马匹的全排列，将每种排列与齐威王的马匹逐一比较。

例如，我们检查以下所有六种对阵情况：

$(t_1, t_2, t_3)$ vs $(q_1, q_2, q_3)$
$(t_1, t_3, t_2)$ vs $(q_1, q_2, q_3)$
$(t_2, t_1, t_3)$ vs $(q_1, q_2, q_3)$
$(t_2, t_3, t_1)$ vs $(q_1, q_2, q_3)$
$(t_3, t_1, t_2)$ vs $(q_1, q_2, q_3)$
$(t_3, t_2, t_1)$ vs $(q_1, q_2, q_3)$

在任何一种情况中，只要田忌获胜的局数 $\ge 2$ ，我们就输出 "Yes"。如果遍历完所有情况，田忌都无法赢得两局或更多，则输出 "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];
    }

    // 对田忌的马速进行排序，方便使用next_permutation
    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++;

        // 如果胜场达到2场或以上
        if (wins >= 2) {
            canWin = true;
            break;
        }
    } while (next_permutation(t.begin(), t.end()));

    if (canWin) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    // 检查某个排列是否能赢
    private static boolean checkWin(int[] q, int[] t) {
        int wins = 0;
        if (t[0] > q[0]) wins++;
        if (t[1] > q[1]) wins++;
        if (t[2] > q[2]) wins++;
        return wins >= 2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] q = new int[3];
        int[] t = new int[3];

        // 读取齐威王的马速
        for (int i = 0; i < 3; i++) {
            q[i] = sc.nextInt();
        }
        // 读取田忌的马速
        for (int i = 0; i < 3; i++) {
            t[i] = sc.nextInt();
        }

        // 穷举田忌马匹的所有6种出场排列
        int t1 = t[0], t2 = t[1], t3 = t[2];
        if (checkWin(q, new int[]{t1, t2, t3}) ||
            checkWin(q, new int[]{t1, t3, t2}) ||
            checkWin(q, new int[]{t2, t1, t3}) ||
            checkWin(q, new int[]{t2, t3, t1}) ||
            checkWin(q, new int[]{t3, t1, t2}) ||
            checkWin(q, new int[]{t3, t2, t1})) {
            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")

算法及复杂度

算法：穷举法 / 枚举全排列。
时间复杂度：由于马匹的数量是固定的 $3$ 匹，田忌的马匹出场顺序共有 $3! = 6$ 种排列。我们需要遍历这 $6$ 种情况，每次比较 $3$ 次。操作次数是常数级别的，因此时间复杂度为 $O(1)$ 。
空间复杂度：我们只需要存储 $6$ 匹马的速度，这是常数级别的空间。因此，空间复杂度为 $O(1)$ 。