美团8.20笔试情况

public class FourthDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();//表示A的长度
        int M = sc.nextInt();//表示B的长度
        int[] A = new int[N];
        int[] B = new int[M];
        for (int i = 0;i < N;i++){
            A[i] = sc.nextInt();
        }
        for (int i = 0;i < M;i++){
            B[i] = sc.nextInt();
        }
        //定义一个dp[i][j]表示A前i个和B的前j个 一样至少需要多少时间
        int[][] dp = new int[N + 1][M + 1];
        for (int i = 1;i <= N;i++){
            for (int j = 1;j <= M;j++){
                if(A[i - 1] == B[j - 1]){
                    //说明这个元素不需要改变就已经相等
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    //如果两者长度一致 则肯定是选择操作一 变换一个元素
                    //如果两者长度不一致，则肯定是选择操作二，删除一个元素
                    if(i == j){
                        //长度一致
                        dp[i][j] = dp[i - 1][j - 1] + Math.abs(A[i - 1] - B[j - 1]);
                    }else if(i < j){
                        //B长
                        dp[i][j] = dp[i][j - 1] + Math.abs(B[j - 1]);
                    }else {
                        //A长
                        dp[i][j] = dp[i - 1][j] + Math.abs(A[i - 1]);
                    }
                }
            }
        }
        System.out.println(dp[N][M]);
    }
}

public class ThirdDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();//一共N道题目
        int M = sc.nextInt();//最多复习M题目，使得M题100%作对！

        int [] P = new int[N];//记录每一题作对的概率
        for (int i = 0;i < N;i++){
            P[i] = sc.nextInt();
        }
        //按照最对概率排序,优先学习得分低的！
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> {
            int p1 = o1[0];
            int score1 = o1[1];
            int p2 = o2[0];
            int score2 = o2[1];
            if(p1 * score1 != p2 * score2){
                return p1 * score1 - p2 * score2;
            }else {
                //概率一样 按分高排序
                return score2 - score1;
            }
        }));
        int[] scores = new int[N];
        for (int i = 0;i < N;i++){
            scores[i] = sc.nextInt();
            queue.offer(new int[]{P[i],scores[i]});
        }

        double maxScores = 0;
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int p = poll[0];
            int score = poll[1];
            if(M-- > 0){
                //100%得分！
                maxScores += score;
            }else {
                //按照概率得分！
                double trueScore = (p * score) / 100d;
                maxScores += trueScore;
            }
        }
        System.out.printf("%.2f",maxScores);
    }
}