美团8.20笔试情况
### 第四题 为什么只a了18(看完评论区,已经懂了没有初始化dp数组!)
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); } }