5.7java美团后端笔试题解_美团java笔试题库及答案

事先说明：

 本文题目转载自 ：(61条消息) Java后端之美团笔试题_最耀眼的那个繁星的博客-CSDN博客

 本文题解转载自：5.7 美团后端笔试 提前20min AK_笔经面经_牛客网

本文是笔者的学习过程，在原有代码上加了一些理解性的注释。 (如侵，则删)

题目一：
小团饲养了一小缸鱼，并且买了A、B、C三类饲料来喂养它们，小团的饲养计划如下：
—— 在每周一、五、六，喂8粒A类饲料；
—— 在每周二、日，喂5颗B类饲料；
—— 在每周三、四，喂7颗C类饲料。
 假设在某个周一，小团一次性购买了A、B、C三类饲料各a、b、c颗，并在当天开始饲养，请问如果小团按照它的饲养计划进行喂食，请问这批饲料可以吃多少天（周一当天也算一天）？

样例输入
8 6 6
样例输出
2
 

 
import java.util.Scanner;
 
public class Main_0 {
    public static void main(String[] args) {
        //模拟
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        //判断能喂食几天
        int da = a /8;
        int db = b /5;
        int dc = c /7;
 
        int res =0;
        for (int i = 1; ;i++) {
            int r = i % 7;
            switch (r){
                case 1:
                case 5:
                case 6:
                    if(da == 0 ){
                        System.out.println(res);
                        return;
                    }
                    da--;
                    res++;
                    break;
                case 0:
                case 2:
                    if(db == 0 ){
                        System.out.println(res);
                        return;
                    }
                    db--;
                    res++;
                    break;
                case 3:
                case 4:
                    if(dc == 0 ){
                        System.out.println(res);
                        return;
                    }
                    dc--;
                    res++;
                    break;
                default: return;
            }
        }
    }
}

题目二：
小美得到了一个只包含’0’和’1’两种字符的字符串，现在她可以往这个字符串的任意位置添加任意个字符’1’，请问她至少需要添加多少个字符’1’才能使添加后的字符串是一个回文串？
输入描述
第一行一个整数T，表示有T组数据。
接下来T行，第i行是一个只包含’0’和’1’两种字符的字符串si。
1<=T<=10, 1<=字符串si的长度<=100000
输出描述
T行，每行一个整数，其中第i行表示输入描述中的字符串si至少需要添加多少个字符’1’使其变成回文串。
样例输入
4
10101
00001
01001101
1110
样例输出
0
1
2
3
样例解释
添加的字串用[]示意：
10101=>10101，无需添加即是回文串。
00001=>[1]00001
01001101=>[1]01[1]001101
1110=>1110[1][1][1]
 

import java.util.Scanner;
 
public class Main_1 {
    public static void main(String[] args) {
        //双指针
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        do {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
 
                arr[i] = add(sc.next());
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.println(arr[i]);
            }
        } while (n >= 1 && n <= 10);
    }
        private static int add(String str){
            int res =0;
            //字符串转成字符型数组
            char[] s=str.toCharArray();
            int l=0,r=s.length-1;
            while(l<r){
                if(s[l] == s[r]){
                    l++;
                    r--;
                }else if(s[l] == '1'){
                    res++;
                    l++;
                }else{
                    res++;
                    r--;
                }
            }
            return res;
        }
}

题目三：
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小团在一个无限长的一维坐标轴上玩一个探险游戏，初始时他位于原点，并有k点体力。每往正方向走一格（无法往反方向移动）需要消耗一点体力。要求小团在任何时刻体力都不能小于零。已知坐标轴上有n个坐标上有体力药水，到达这些坐标时，可以恢复一定量的体力。小团想知道，他所能到达的最远坐标是多远？
<p>
输入描述
第一行两个正整数k、n，分别表示小团初始有k点体力，以及坐标轴上有n个坐标上有体力药水。
接下来一行n个正整数，第i个数xi表示在xi这个坐标上有体力药水。（xi互不相同）
接下来一行n个正整数，第i个数ti表示在xi这个坐标上的体力药水可以恢复ti点体力。
1<=k <=2000000, 1<=n<=20000,1<=xi<=100000000,1<= ti<=10000
输出描述
一行一个正整数，表示小团所能到达的最远坐标。
样例输入
5 2
6 3
1 2
样例输出
8
提示
样例解释1
初始有5点体力，到达坐标3时还剩余2点体力，补充2点，共余4点；
到达坐标6时还剩下1点，补充1点，共余2点；
耗尽体力时处于坐标8。
输入样例2
2 1
2
1
输出样例2
3
样例解释2
初始有2点体力，在坐标2补充1点体力到达坐标3。
输入样例3
2 1
3
1
输出样例3
2
样例解释3
初始有2点体力，到达坐标2耗尽体力停止。
 

import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main_2 {
    public static void main(String[] args) {
        //底层逻辑——预排序+模拟
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
        }
        //案例
        // 5 2
        // 6 3
        // 1 2
        // 输出8
        PriorityQueue<int[]> que = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            //优先队列 默认是小顶堆 最小元素在堆顶
            que.add(new int[]{x[i],t[i]});
            //[3,2] [6,1]
        }
        //判断站点
        int res = 0;
        while(!que.isEmpty()){
            //取堆顶，且去除，先[3,2]再[6,1]
            int[] xt = que.poll();
            //剩余体力是否能到达第一个点
            if (k + res < xt[0]){
                res += k;
                System.out.println(res);
                return;
            } else {
                //能的话，先吧到第一个点剩余体力算出来，然后加上奖励的体力
                //此时站点在xt[0]->(赋值给)res
                k -= xt[0] - res;
                k += xt[1];
                res = xt[0];
            }
        }
        //都执行结束，还有体力就多走k步
        System.out.println(res + k);
    }
}

题目四：
代金券
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美和小团来到了一家餐厅吃饭，美团上有许多代金券，形如花xi元购买，可以当yi元使用(保证yi>xi)。至多只能购买一张代金券。
对于餐厅里的每种菜品，有价格ai和能够给予给他们的满意度bi。每种菜品至多只会点一份。
代金券是一次性无找零的，若本次消费的价格不高于代金券可以抵用的价格，那么可以使用代金券来抵付本次的所有消费；若本次消费的价格高于可抵用价格，那么还需要支付超出的部分。

下面给出两个例子：
——如果本次需要消费270元，小美和小团花了250元购买了一张可以抵300元的代金券，那么使用这张代金券可以完全抵付，他们实际花费250元；
——如果本次消费需要230元，小美和小团花了150元购买了一张可以抵199的代金券，那么他们使用代金券可以抵199元，但还需要支付超出的230-199=31元，他们实际花费150+31=181元。
假设他们这次吃饭的预算是k元，请问他们能得到的最高满意度是多少？

输入描述
第一行3个整数n、m、k，分别表示美团上有n种代金券、餐厅的菜单上有m种菜品、以及小美和小团的预算是k元。
接下来n行，每行两个整数，第 i 行xi和yi分别表示代金券的价格为xi元，可以抵用yi元。
接下来m行，每行两个整数，第i行ai和bi分别表示菜品的价格为ai元，该菜品可以给予他们的满意度为bi。
1<=n<=20,1<=m<=200, 1<=k<=10000, 1<=xi<=yi<=20000, 1<=ai,bi<=500
输出描述
输出一个整数，表示小美和小团在预算内最多能获得多高的满意度。
样例输入
2 3 10
7 10
10 12
7 4
2 4
5 6
样例输出
10
提示
样例解释
点的菜品为第1种与第3种，满意度为10，需要支付12元。
可以选择第一种代金券，抵用10元再额外支付2元，一共花费7+2=9元，在预算内；
也可以选择第二种代金券，直接抵用12元，无需额外再支付，花费10元，在预算内。
 

import java.util.Scanner;
 
public class Main_3 {
    public static void main(String[] args) {
        //背包问题，动态规划（dp）
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // n种代金券
        int m = sc.nextInt();
        // m种菜品
        int k = sc.nextInt();
        // k预算金额
        int money = k;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            if(k > x) {money = Math.max(k-x+y,money);}
            //节省几块
        }
        int[] w = new int[m];
        //价格
        int[] v = new int[m];
        //满意度
        for (int i = 0; i < m; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
 
        int[][] dp = new int[m + 1][money + 1];
        //dp[i][j]：使用 j钱 在 前i个菜品中选获得的最大满意度
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= money; j++) {
                if (j > w[i-1]){
                    //'背包能装下'
                    dp[i][j] = Math.max(dp[i-1][j-w[i-1]] + v[i-1], dp[i-1][j]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[m][money]);
    }
}