美团2021校招笔试-编程题(通用编程试题,第9场)_1. 糕点 小团的蛋糕铺长期霸占着美团ap

题目一：糕点

题目描述：小团的蛋糕铺长期霸占着美团APP中“蛋糕奶茶”栏目的首位，因此总会吸引各路食客前来探店。
小团一天最多可以烤n个蛋糕，每个蛋糕有一个正整数的重量。

早上，糕点铺已经做好了m个蛋糕。

现在，有一个顾客要来买两个蛋糕，他希望买这一天糕点铺烤好的最重的和最轻的蛋糕，并且希望这两个蛋糕的重量恰好为a和b。剩余的n-m个蛋糕可以现烤，请问小团能否满足他的要求？

输入描述：

输入包含多组数据，每组数据两行。

每组数据的第一行包含4个整数，n,m,a,b，空格隔开。这里不保证a和b的大小关系。

接下来一行m个数，空格隔开，代表烤好的蛋糕重量

输出描述：

对于每一组数据，如果可以办到顾客的要求，输出YES，否则输出NO

样例：

输入：
4 2 2 4
3 3
4 2 2 4
1 1
4 2 2 4
5 5
4 2 4 2
2 4
2 2 2 4
3 3
3 2 2 4
3 3
3 2 2 4
3 3
输出：
YES
NO
NO
YES
NO
NO
NO
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路：题意蛮简单，只需要对剩下的n-m进行分类讨论即可。
代码：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            int n=cin.nextInt();
            int m=cin.nextInt();
            int a=cin.nextInt();
            int b=cin.nextInt();
            if(a>b){ //保证a小b大
                a=a+b;
                b=a-b;
                a=a-b;
            }
            
            int maxNum=0,minNum=Integer.MAX_VALUE;
            for(int i=0;i<m;i++){ //记录当前最大值和最小值
                int x=cin.nextInt();
                maxNum=Math.max(maxNum,x);
                minNum=Math.min(minNum,x);
            }
            int rest=n-m;
            int flag=0;
            if(rest==0&&a==minNum&&b==maxNum) flag=1;
            if(rest==1&&(a==minNum||b==maxNum)) flag=1;
            if(rest>=2&&minNum>=a&&maxNum<=b) flag=1; //区间包含才行
            if(flag==1) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

题目二：晋级人数
题目描述：小团是某综艺节目的策划，他为某个游戏环节设计了一种晋级规则，已知在这个游戏环节中每个人最后都会得到一个分数score_i，显而易见的是，游戏很有可能出现同分的情况，小团计划该环节晋级人数为x人，则将所有人的分数从高到低排序，所有分数大于等于第x个人的分数且得分不为0的人都可以晋级。

请你求出本环节的实际晋级人数。显然这个数字可能是0，如果所有人的得分都是0，则没有人满足晋级条件。
输入描述：

输入第一行包含两个正整数n和x，分别表示参加本环节的人数，和小团指定的x。
输入第二行包含n个整数，每个整数表示一位选手的得分。

输出描述：

输出仅包含一个整数，表示实际晋级人数。

样例：

输入：
5 4 
0 0 2 3 4
输出：
3
1
2
3
4
5

思路：排个序按照题意找就完事儿。

import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            int n=cin.nextInt();
            int x=cin.nextInt();
            int nums[]=new int[n];
            for(int i=0;i<n;i++) nums[i]=cin.nextInt();
            Arrays.sort(nums);
            int ans=0;
            for(int i=0;i<n;i++){
                if(nums[i]!=0&&nums[i]>=nums[n-x]) ans++;
            }
            System.out.println(ans);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

题目三：回转寿司
题目描述：小美请小团吃回转寿司。转盘上有N盘寿司围成一圈，第1盘与第2盘相邻，第2盘与第3盘相邻，…，第N-1盘与第N盘相邻，第N盘与第1盘相邻。小团认为第i盘寿司的美味值为A[i]（可能是负值，如果小团讨厌这盘寿司）。现在，小团要在转盘上选出连续的若干盘寿司，使得这些寿司的美味值之和最大（允许不选任何寿司，此时美味值总和为0）。

输入描述：

第一行输入一个整数T（1<=T<=10），表示数据组数。

每组数据占两行，第一行输入一个整数N（1<=N<=10^5）；

第二行输入N个由空格隔开的整数，表示A[1]到A[N]（-10^4<=A[i]<=10^4）。

输出描述：

每组数据输出占一行，输出一个整数，表示连续若干盘寿司的美味值之和的最大值。

样例:

输入：
1
4
3 -2 4 -1
输出：
6
1
2
3
4
5
6

思路：其实就是最大连续子数组和变种，主要是这里形成了环。常规解法就是在原来解最大连续子数组和基础上，将这个数组元素复制一遍，按照区间求即可，时间复杂度为O(n^2)，原因是多了一次枚举固定长度为n的区间，直接TLE。
PASS掉这种暴力想法，想想原来的最大连续子数组和怎么求，记录当前子数组最大值和全局最大值。这里形成了环，就有两种情况了，一是首尾相连之后对整个环的最大和没贡献，这种我们直接按照原本的最大连续子数组和计算。第二种是首尾相连之后添加了贡献，因此可能会出现首尾相连之后连续和更大，对于这种情况我们直接按照原来方法求一遍连续子数组和最小，然后用所有数的和（sum）减去这个连续子数组的最小值和原来求连续子数组的全局最大值取一个max即可。原因在于我们的sum求的是所有的数的和，这中间不乏计算了连续子数组和为负数的情况，因此我们将这个最小连续子数组和求出来，再用sum来减掉这个最小连续子数组和就成了首尾相连计算的情况。

代码：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            int T=cin.nextInt();
            while(T-->0){
                int n=cin.nextInt();
                int nums[]=new int[n];
                int sum=0;
                for(int i=0;i<n;i++){
                    nums[i]=cin.nextInt();
                    sum+=nums[i];
                }
                int maxSum=nums[0],curMaxSum=nums[0];
                int minSum=nums[0],curMinSum=nums[0];
                for(int i=1;i<n;i++){
                    curMaxSum=Math.max(nums[i],nums[i]+curMaxSum);
                    maxSum=Math.max(maxSum,curMaxSum);
                    curMinSum=Math.min(nums[i],nums[i]+curMinSum);
                    minSum=Math.min(minSum,curMinSum);
                }
                System.out.println(Math.max(sum-minSum,maxSum));
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27