当前位置：首页 > article >正文

OJ-1014田忌赛马

article 2025/3/9 10:56:49

示例1：

输入
11 8 20
10 13 7
输出
1

示例2：
输入
11 12 20
10 13 7
输出
2

示例3：
输入
1 2 3
4 5 6
输出
6

解题思路：

问题的关键在于调整数组a的顺序,使得尽可能多的a[i] > b[i]。为了达到最优结果,我们可以采用贪心的策略。具体思路如下:

1.首先，将数组a按照从大到小的顺序排序。
2.对于数组b,我们需要找到与每个b[i]相对应的最小的a[j],使得a[j]>b[i]。为了实现这一点,我们可以采用二分查找,找到a中第一个大于b[i]的数字的索引。
3.如果找到了对应的a[j],则将a[j]标记为已使用,并继续处理下一个b[i]。
4.如果没有找到对应的a[j],说明当前的b[i]无法找到满足条件的a[j],则尝试找下一个b[i+1]对应的a[j]。
5·重复以上步骤,直到处理完所有的b[i]。
最后,统计所有满足条件的a数组排列的数量即可。这样的贪心策略能够保证尽可能多的a[i]> b[i]。
在实际实现中，可以使用递归或迭代的方式来生成所有可能的a数组排列，然后根据上述贪心策略进行筛选。最终输出满足条件的a数组排列的数量。

优化：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class 田忌赛马 {
    static Map<Integer, Integer> cnts = new HashMap<>();
    static int[] a;
    static int[] b;
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        a = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        b = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = a.length;

        boolean[] st = new boolean[n];
        int[] nums = new int[n];

        dfs(0, st, nums);

        int maxcnt = 0;
        for (int k : cnts.keySet()) {
            if (k > maxcnt) {
                maxcnt = k;
            }
        }
        System.out.println(cnts.get(maxcnt));
    }

    private static void dfs(int u, boolean[] st, int[] nums) {
        if (u == n) {
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] > b[i]) {
                    cnt += 1;
                }
            }
            cnts.put(cnt, cnts.getOrDefault(cnt, 0) + 1);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (st[i]) continue;
            st[i] = true;
            nums[u] = a[i];
            dfs(u + 1, st, nums);
            st[i] = false;
        }
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;


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

        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        
        String[] s1 = scanner.nextLine().split(" ");
        String[] s2 = scanner.nextLine().split(" ");

        for (int i = 0; i < s1.length; i++) {
            a.add(Integer.parseInt(s1[i]));
            b.add(Integer.parseInt(s2[i]));
        }

        // 对列表a进行排序
        Collections.sort(a);

        int n = a.size();
        boolean[] st = new boolean[n];
        int[] nums = new int[n];
        Map<Integer, Integer> cnts = new HashMap<>();

        // 调用深度优先搜索函数
        dfs(0, a, b, st, nums, cnts);

        int maxcnt = 0, maxnum = cnts.getOrDefault(0, 0);

        // 寻找最大的相同数字数量和对应的排列情况数量
        for (Map.Entry<Integer, Integer> entry : cnts.entrySet()) {
            int k = entry.getKey();
            int v = entry.getValue();
            if (k > maxcnt) {
                maxcnt = k;
                maxnum = v;
            }
        }

        // 输出最大的相同数字数量
        System.out.println(maxnum);
    }

    // 定义深度优先搜索函数
    private static void dfs(int u, List<Integer> a, List<Integer> b, boolean[] st, int[] nums, Map<Integer, Integer> cnts) {
        // 如果已经遍历完所有数字，进行统计
        if (u == a.size()) {
            int cnt = 0;
            for (int i = 0; i < a.size(); i++) {
                if (nums[i] > b.get(i)) {
                    cnt += 1;
                }
            }
            cnts.put(cnt, cnts.getOrDefault(cnt, 0) + 1);
            return;
        }

        // 遍历数字进行排列
        for (int i = 0; i < a.size(); i++) {
            // 如果当前数字已经被选择或者当前数字和前一个数字相同，做一个去重操作
            if (st[i] || (i > 0 && a.get(i).equals(a.get(i - 1)) && st[i - 1])) {
                continue;
            }
            st[i] = true;
            nums[u] = a.get(i);
            dfs(u + 1, a, b, st, nums, cnts);
            st[i] = false;
        }
    }
}