小米笔试9/19-装箱+排序挑战

第一题：装箱（动态规划）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int N = sc.nextInt(), n = sc.nextInt(), c = sc.nextInt(); // 容量 + 玩具个数 + 填充物个数
            int[] a = new int[n + c];
            for (int j = 0; j < n; j++) {
                a[j] = sc.nextInt();
            }
            for (int j = n; j < n + c; j++) {
                a[j] = 1;
            }
            boolean res = checkFull(N, n, a);

            if (res) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        sc.close();
    }

    private static boolean checkFull(int N, int c, int[] a) {
        if (N <= c)
            return true;
        boolean[][] dp = new boolean[a.length][N + 1];
        if (a[0] <= N) {
            dp[0][a[0]] = true;
        }
        for (int i = 0; i < a.length; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i < a.length; i++) {
            for (int j = 1; j <= N; j++) {
                if (a[i] <= j) {
                    dp[i][j] = dp[i - 1][j - a[i]];
                }
                dp[i][j] = dp[i][j] || dp[i - 1][j];
            }
        }

        return dp[a.length - 1][N];
    }
}

第二题：排序挑战（贪心）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = sc.nextInt();
            }
            int[] b = new int[n];
            for (int j = 0; j < n; j++) {
                b[j] = sc.nextInt();
            }
            boolean res = checkCanExchange(a, b, n);
            if (res) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        sc.close();
    }

    private static boolean checkCanExchange(int[] a, int[] b, int n) {
        return checkUp(a, b) || checkUp(b, a) || checkDown(a, b) || checkDown(b, a);
    }

    private static boolean checkDown(int[] a, int[] b) {
        int n = a.length;
        int[] target = new int[n];
        int[] other = new int[n];
        for (int i = 0; i < n; i++) {
            target[i] = a[i];
            other[i] = b[i];
        }
        int pre = 10001;
        for (int i = 1; i < n; i++) {
            int minV = Math.min(target[i], other[i]);
            int maxV = Math.max(target[i], other[i]);
            if (maxV <= pre) {
                target[i] = maxV;
                pre = target[i];
            } else {
                if (minV <= pre) {
                    target[i] = minV;
                    pre = target[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean checkUp(int[] a, int[] b) {
        int n = a.length;
        int[] target = new int[n];
        int[] other = new int[n];
        for (int i = 0; i < n; i++) {
            target[i] = a[i];
            other[i] = b[i];
        }
        int pre = 0;
        for (int i = 0; i < n; i++) {
            int minV = Math.min(target[i], other[i]);
            int maxV = Math.max(target[i], other[i]);
            if (minV >= pre) {
                target[i] = minV;
                pre = target[i];
            } else {
                if (maxV >= pre) {
                    target[i] = maxV;
                    pre = target[i];
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}