美团2023届秋招技术综合0820

编程题1==AC==

编程题|20.0分1/4

烤串

时间限制： 3000MS
内存限制： 589824KB

题目描述：

小团想要自己来烤串！不过在烤串之前，需要串好烤串。小团有n个荤菜和n个素菜，他想按顺序分别一个荤菜一个素菜串起来，想请你帮他串好！给出两个长度分别为n的仅包含小写英文字母的串A和B，分别代表荤菜和素菜的种类（用字母来表示菜的种类）。请你以从左到右的顺序依次串好他们！例如对于荤菜串A1A2…An和素菜串B1B2…Bn，串好应该是A1B1A2B2…AnBn

输入描述

第一行一个正整数n，表示烤串长度

第二行为一个长度为n的字符串A，表示荤菜按次序都是哪些菜。

第三行为一个长度为n的字符串B，表示素菜按次序都是哪些菜。

对于80%的数据，n≤1000

对于20%的数据，n≤50000

对于所有数据，A和B为仅包含小写英文字母的字符串。

输出描述

输出一行，包含2n个字符串表示串好的烤串。

样例输入

1
2
3

4
abcd
efgh

样例输出

1	`aebfcgdh`

提示

1	`按规则A1B1A2B2...AnBn串好即可。`

规则

请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果
点击“调试”亦可保存代码
编程题可以使用本地编译器，此页面不记录跳出次数

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String meat = scanner.nextLine(), vegetable = scanner.nextLine();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++)
            sb.append(meat.charAt(i)).append(vegetable.charAt(i));
        System.out.println(sb);
    }
}

编程题2==AC==

编程题|20.0分2/4

定位

时间限制： 3000MS
内存限制： 589824KB

题目描述：

小团在地图上放了三个定位装置，想依赖他们来进行定位！小团的地图是一个n×n的一个棋盘，他在(x1,y1),(x2,y2),(x3,y3) xi,yi ∈ Z ∩ [1,n] 这三个位置分别放置了一个定位装置（两两不重叠）。然后小团在一个特定的位置(a,b)a,b ∈ Z ∩ [1,n]放置了一个信标。每个信标会告诉小团它自身到那个信标的曼哈顿距离，即对i=1,2,3 小团知道(|xi-a|+|yi-b|)，现在小团想让你帮他找出信标的位置！注意，题目保证最少有一个正确的信标位置。因为小团不能定位装置确定出来的信标位置是否唯一，如果有多个，输出字典序最小的那个。(a,b)的字典序比(c,d)小，当且仅当 a<c或者a==c∧b<d

输入描述

第一行一个正整数n，表示棋盘大小。

第二行两个整数，分别表示x1与y1，即第一个定位器的位置。

第三行两个整数，分别表示x2与y2，即第二个定位器的位置。

第四行两个整数，分别表示x3与y3，即第三个定位器的位置。

第五行三个整数，分别表示第一、二、三个定位器到信标的曼哈顿距离。第i个定位器到信标的曼哈顿距离即(|xi-a|+|yi-b|)

数字间两两有空格隔开，对于所有数据， n≤50000, 1≤xi,yi≤n

输出描述

输出一行两个整数，表示字典序最小的可能的信标位置。

样例输入

样例输出

1 2

提示

样例解释：与 (2, 1) 的哈曼顿距离为2的位置有三个，分别是 (1, 2), (2, 3), (3, 2)与 (2, 2) 的哈曼顿距离为1的位置有四个，分别是 (1, 2), (2, 1), (2, 3), (3, 2)与 (2, 3) 的哈曼顿距离为2的位置有三个，分别是 (1, 2), (2, 1), (3, 2)所以只有 (1, 2), (3, 2) 这两个位置有可能是信标，而 (1, 2) 的字典序最小，所以输出 (1, 2)

规则

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] base = new int[3][2];
        for(int i = 0; i < 3; i++) {
            base[i][0] = scanner.nextInt();
            base[i][1] = scanner.nextInt();
        }

        int[] distance = new int[3];
        Map<String, Integer> map = new HashMap<>();
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            distance[i] = scanner.nextInt();
            List<int[]> temp = addPoints(base[i], distance[i], n);
            for (int[] t : temp) {
                String key = String.valueOf(t[0]) + " " + String.valueOf(t[1]);
                map.put(key, map.getOrDefault(key, 0) + 1);
                if (map.get(key) == 3)
                    ans.add(key);
            }
        }

        Collections.sort(ans);
        System.out.println(ans.get(0));

    }

    public static List<int[]> addPoints(int[] base, int distance, int N) {
        List<int[]> ans = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (Math.abs(base[0] - i) + Math.abs(base[1] - j) == distance) {
                    ans.add(new int[]{i, j});
                }
            }
        }
        return ans;
    }
}

编程题3==73%==

编程题|20.0分3/4

复习

时间限制： 3000MS
内存限制： 589824KB

题目描述：

小美即将进行期末考试！小美现在盘算了一下，一共有n道试题，对于第 i 道试题，小美有着pi的概率做对，获得ai的分值，另外(1-pi)的概率做错，获得0分。小美的总分即是每道题获得的分数之和。小美不甘于此！她决定突击复习，因为时间有限，她最多复习m道试题，使得复习后的试题正确率提升到100%。小美想知道，如果她以最佳方式进行复习，能获得的期望总分最大是多少。

输入描述

第一行两个正整数n和m，表示总试题数和最多复习试题数。

接下来一行n个整数，分别为p1 p2…pn，表示小美有pi%的概率，即pi=pi/100的概率做对第i个题。（注意，这里为了简单起见，将概率pi扩张100倍成为整数pi方便输入）

接下来一行n个整数，分别表示a1 a2…an，分别表示第 i 个题做对的分值。

数字间两两有空格隔开，对于所有数据，1≤m≤n≤50000,0≤pi≤100,1≤ai≤1000

输出描述

输出一行一个恰好两位的小数，表示能获得的最大期望总分。（如果答案为10应输出10.00，2.5应输出2.50）

样例输入

1
2
3

2 1
89 38 
445 754

样例输出

1150.05

提示

如果都不复习，小美总分的期望为89%*445+38%*754=682.57如果复习第一道题，小美总分的期望为100%*445+38%*754=731.52如果复习第二道题，小美总分的期望为89%*445+100%*754=1150.05所以选择复习第二道题，这样能获得最大期望总分1150.05根据每题复习后的收益进行排序即可

规则

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++)
            nums[i][0] = scanner.nextInt();
        for (int i = 0; i < n; i++)
            nums[i][1] = scanner.nextInt();	

        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
//                return o1[1] == o2[1] ? o1[0] - o2[0] : o2[1] - o1[1];
                int temp = (100 - o2[0]) * o2[1] - (100-o1[0]) * o1[1];
                return temp == 0 ? o2[1] - o1[1] : temp;
            }
        });

        long ans = 0L;
        for (int i = 0; i < m; i++)
            ans += nums[i][1];

        long ans2 = 0L;
        for (int i = m; i < n; i++)
            ans2 += (long) nums[i][0] * nums[i][1];

        double res = (double) ans + ans2 / 100.0;
        System.out.println(res);
    }
}

编程题4

编程题|20.0分4/4

拟合

时间限制： 3000MS
内存限制： 589824KB

题目描述：

小团生日收到妈妈送的两个一模一样的数列作为礼物！他很开心的把玩，不过不小心没拿稳将数列摔坏了！现在他手上的两个数列分别为A和B，长度分别为n和m。小团很想再次让这两个数列变得一样。他现在能做两种操作，操作一是将一个选定数列中的某一个数a改成数b，这会花费|b-a|的时间，操作二是选择一个数列中某个数a，将它从数列中丢掉，花费|a|的时间。小团想知道，他最少能以多少时间将这两个数列变得再次相同！

输入描述

第一行两个空格隔开的正整数n和m，分别表示数列A和B的长度。

接下来一行n个整数，分别为A1 A2…An

接下来一行m个整数，分别为B1 B2…Bm

对于所有数据，1≤n,m≤2000， |Ai|,|Bi|≤10000

输出描述

输出一行一个整数，表示最少花费时间，来使得两个数列相同。

样例输入

1
2
3

1 1
-9821 
7742

样例输出

提示

可以选择两次第二种操作，消除数列A的第一个数和数列B的第一个数，需要花费9821+7742=17563的时间也可以选择一次第一种操作，将数列A的第一个数改成数列B的第一个数，也是需要花费9821+7742=17563的时间所以答案为17563

规则

编程题5

编程题|20.0分1/1

修补

时间限制： 3000MS
内存限制： 589824KB

题目描述：

小团的玩具火箭有点磨损了，上面有很多地方翘起来了，小团想要用强力胶进行修补，但在强力胶凝结之前，需要找点东西压住。幸好小团有很多这样的东西。小团有m种配重材料，第i种材料重ai单位重量（因为小团有太多了，可以认为每种都有任意多个）。火箭上有n个地方翘起来了，需要至少bi单位重量的东西来压住，而且只能用一个配重材料来压，(多了的话不好压，多个配重材料容易散开，所以小团不想用多个来折腾)。小团想一次就把所有翘起来的地方全都修补好，请问他需要使用的配重材料重量之和最少是多少？

输入描述

第一行两个正整数n和m，分别代表需要修补的地方个数以及材料种类数。

接下来一行n个数b1,b2,…,bn，含义如题。

接下来一行m个数 a1,a2,…,am，含义如题。

对于40%的数据，n,m≤100

对于另外30%的数据，n,m≤2000

对于所有数据，1≤n,m≤50000，1≤ai,bi≤104

输出描述

输出小团最少需要使用的配重材料重量之和。如果没有任何办法满足，输出-1

样例输入

1
2
3

1 1
5
4

样例输出

-1

提示

样例1解释需要5单位重量，只有4单位重量的材料，压不住，输出-1。
输入样例2

1
2
3

3 3
4 1 3
4 2 1

输出样例2

样例解释2第一个地方需要重量为4的，第二个地方可以用重量为1的，第三个地方只能选择重量为4的才能压住。所以总重量需求为9。可以证明没有更优方案。

规则

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[] b = new int[n], a = new int[m];
        for (int i = 0; i < n; i++)
            b[i] = scanner.nextInt();
        for (int i = 0; i < m; i++)
            a[i] = scanner.nextInt();

        Arrays.sort(a);

        long res = 0;
        for (int i = 0; i < n; i++) {
            int temp = binarySearch(a, b[i]);
            if (temp == -1) {
                System.out.println("-1");
                return ;
            }
            res += temp;
        }

        System.out.println(res);

    }

    public static int binarySearch(int[] nums, int val) {
        int n = nums.length;
        if (nums[n-1] < val)
            return -1;
        int left = 0, right = n-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < val)
                left = mid + 1;
            else
                right = mid;
        }
        return nums[right];
    }
}

笔试

#Java #笔试 #offer #后端开发 #美团

美团2023届笔试第三批

http://example.com/2022/08/20/笔试记录/美团2023届秋招-技术综合0820/

作者

madao33

发布于

August 20, 2022

许可协议

网易2023届秋季校园招聘笔试0820-通用技术上一篇

654.最大二叉树下一篇

美团笔试记录

美团2023届秋招 技术综合0820

编程题1==AC==

编程题2==AC==

编程题3==73%==

编程题4

编程题5

美团2023届秋招技术综合0820