田忌赛马

思路

拿到这道题，第一反应是什么？三匹马对三匹马，田忌可以自由安排出场顺序，问能不能赢至少两局。

那田忌的马一共有多少种出场顺序？3 匹马的全排列，也就是 种。数量这么少，直接暴力枚举所有排列不就行了？

具体做法

  1. 读入齐威王的三匹马速度（顺序固定），以及田忌的三匹马速度
  2. 对田忌的马生成所有排列（一共 6 种）
  3. 对每种排列，逐局比较：田忌的马速度严格大于齐威王的马才算赢
  4. 只要存在某种排列能赢 2 局及以上，输出 Yes；否则输出 No

这题的关键点就一个：严格大于才算赢，等于不算。比如样例 2 里田忌有一匹速度为 3 的马，但另外两匹都是 2，和齐威王的 2 打平，赢不了两局。

代码

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

int main() {
    int a[3], b[3];
    for (int i = 0; i < 3; i++) cin >> a[i];
    for (int i = 0; i < 3; i++) cin >> b[i];

    // 枚举田忌马匹的所有排列
    sort(b, b + 3);
    do {
        int win = 0;
        for (int i = 0; i < 3; i++) {
            if (b[i] > a[i]) win++;  // 严格大于才赢
        }
        if (win >= 2) {
            cout << "Yes" << endl;
            return 0;
        }
    } while (next_permutation(b, b + 3));

    cout << "No" << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static int[] a = new int[3], b = new int[3];
    static boolean found = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 3; i++) a[i] = sc.nextInt();
        for (int i = 0; i < 3; i++) b[i] = sc.nextInt();

        // 枚举田忌马匹的所有排列
        permute(0);
        System.out.println(found ? "Yes" : "No");
    }

    static void permute(int idx) {
        if (found) return;
        if (idx == 3) {
            int win = 0;
            for (int i = 0; i < 3; i++) {
                if (b[i] > a[i]) win++;  // 严格大于才赢
            }
            if (win >= 2) found = true;
            return;
        }
        for (int i = idx; i < 3; i++) {
            // 交换生成排列
            int tmp = b[idx]; b[idx] = b[i]; b[i] = tmp;
            permute(idx + 1);
            tmp = b[idx]; b[idx] = b[i]; b[i] = tmp;
        }
    }
}

from itertools import permutations

a = list(map(int, input().split()))
b = list(map(int, input().split()))

for perm in permutations(b):
    win = sum(1 for i in range(3) if perm[i] > a[i])
    if win >= 2:
        print("Yes")
        exit()
print("No")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const a = lines[0].split(' ').map(Number);
    const b = lines[1].split(' ').map(Number);

    function permute(arr) {
        if (arr.length <= 1) return [arr];
        const result = [];
        for (let i = 0; i < arr.length; i++) {
            const rest = arr.slice(0, i).concat(arr.slice(i + 1));
            for (const perm of permute(rest)) {
                result.push([arr[i], ...perm]);
            }
        }
        return result;
    }

    for (const perm of permute(b)) {
        let win = 0;
        for (let i = 0; i < 3; i++) {
            if (perm[i] > a[i]) win++;
        }
        if (win >= 2) {
            console.log("Yes");
            return;
        }
    }
    console.log("No");
});

复杂度分析

  • 时间复杂度: ，固定 3 匹马，最多枚举 6 种排列，每种比较 3 次
  • 空间复杂度: ，只用了固定大小的数组

总结

这题就是个纯暴力枚举题，3 匹马的全排列才 6 种，没什么花活可玩。C++ 里 next_permutation 用起来很方便，记得先 sort 一下保证从最小排列开始。Java 没有现成的全排列函数，手写一个递归交换就好了。唯一要注意的就是"严格大于"这个条件，等于不算赢。