首页 > 试题广场 >

田忌赛马

[编程题]田忌赛马
  • 热度指数:23454 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}田忌与齐威王正在赛马,比赛一共三局,三局两胜,当一方马匹速度严格大于另一方时获胜,每匹马只能出场一次。
\hspace{15pt}现在你已经知道了齐威王的马匹上场的顺序,将在第一、二、三场上场的马匹速度分别为 v_1,v_2,v_3。同时,你也已经知道了田忌所拥有的马匹速度,分别为 a_1,a_2,a_3
\hspace{15pt}你可以调整田忌的马匹出场顺序,你能否帮助田忌赢得这场比赛?

输入描述:
\hspace{15pt}第一行输入三个整数 v_1,v_2,v_3 \left(1 \leq v_i \leq 9\right) 代表齐威王按上场顺序的马匹速度。
\hspace{15pt}第二行输入三个整数 a_1,a_2,a_3 \left(1 \leq a_i \leq 9\right) 代表田忌拥有的马匹速度。顺序可以任意调整。


输出描述:
\hspace{15pt}如果田忌可以获胜,直接输出 \rm Yes,否则输出 \rm No
示例1

输入

3 2 1
1 2 3

输出

Yes

说明

\hspace{15pt}在这个样例中,田忌可以在第一局派出速度为 1 的马匹,在第二局派出速度为 3 的马匹,在第三局派出速度为 2 的马匹。如此一来,他会赢得两局比赛,从而获胜。
示例2

输入

2 2 2
2 2 3

输出

No
// 枚举法
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取齐威王的马匹速度(按出场顺序)
        int v1 = scanner.nextInt();
        int v2 = scanner.nextInt();
        int v3 = scanner.nextInt();

        // 读取田忌的马匹速度(顺序可调整)
        int a1 = scanner.nextInt();
        int a2 = scanner.nextInt();
        int a3 = scanner.nextInt();

        scanner.close();

        // 所有可能的出场顺序组合
        int[][] permutations = {
            {a1, a2, a3},
            {a1, a3, a2},
            {a2, a1, a3},
            {a2, a3, a1},
            {a3, a1, a2},
            {a3, a2, a1}
        };

        // 检查每种顺序是否能赢
        for (int[] order : permutations) {
            int wins = 0;
            // 第一局
            if (order[0] > v1) wins++;
            // 第二局
            if (order[1] > v2) wins++;
            // 第三局
            if (order[2] > v3) wins++;

            // 赢两局或以上则获胜
            if (wins >= 2) {
                System.out.println("Yes");
                return;
            }
        }

        // 所有顺序都不能赢
        System.out.println("No");
    }
}

发表于 2025-08-17 16:38:18 回复(0)
用的回溯模版,遍历所有的可能性就行了
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

static boolean win_f = false;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int [] qi = new int[3];
int [] tian = new int[3];
int l = 0;
while (in.hasNextLine()) {
String [] s = in.nextLine().split(" ");
for (int i = 0; i < s.length; i++) {
if (l == 0) {
qi[i] = Integer.valueOf(s[i]);
} else {
tian[i] = Integer.valueOf(s[i]);
}
}
l++;
}
int [] vis = new int[3];
backtrack(0, tian, qi, 0, vis );
if (win_f) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}

public static void backtrack(int n, int[] tian, int[] qi, int win,
int [] vis ) {
if (win >= 2 && n == 3) {
win_f = true;
return;
}

for (int i = 0; i < tian.length; i++) {
if (vis[i] == 0) {
vis[i] = 1;
if (tian[i] > qi[n]) {
backtrack(n + 1, tian, qi, win + 1, vis);
} else {
backtrack(n + 1, tian, qi, win, vis);
}
vis[i] = 0;
}
}

}
}
发表于 2025-08-06 21:01:21 回复(0)
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        int[] tian = new int[3];
        int[] qi = new int[3];
        for (int i = 0; i < 2; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            if (i == 0) {
                qi[0] = a;
                qi[1] = b;
                qi[2] = c;
            } else {
                tian[0] = a;
                tian[1] = b;
                tian[2] = c;
            }
        }

        Arrays.sort(qi);
        Arrays.sort(tian);
        if (tian[2] > qi[0] && tian[1] > qi[0]) {
            System.out.print("Yes");
        } else {
            System.out.print("No");
        }
    }
}

发表于 2025-07-20 10:49:49 回复(1)