糕点

[编程题]糕点

热度指数：11080 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小团的蛋糕铺长期霸占着美团APP中“蛋糕奶茶”栏目的首位，因此总会吸引各路食客前来探店。

小团一天最多可以烤n个蛋糕，每个蛋糕有一个正整数的重量。

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

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

数据范围： $1 \le m \le n \le 1000\$ ， $1\le a,b \le 1000\$

进阶：时间复杂度 $O(m)\$ ,空间复杂度 $O(m)\$

输入描述:

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

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

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

输出描述:

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

示例1

输入

输出

YES
NO
NO
YES
NO
NO
NO

备注:

对于40%的数据， $m\leq 10$

对于100%的数据， $1\leq n,m,a,b\leq 1000, m\leq n$ ,蛋糕重量不会超过1000

算法知识视频讲解

Java

卷笔刀坏了

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt(), m = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
            int cake, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int i = 0; i < m; i++) {
                cake = sc.nextInt();
                min = Math.min(min, cake);
                max = Math.max(max, cake);
            }
            if (a > b) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            if (min < a || max > b
                    || (((min > a && max == b) || (min == a && max < b)) && n - m < 1)
                    || (min > a && max < b && n - m < 2)
            ) System.out.println("NO");
            else System.out.println("YES");
        }
    }
}

编辑于 2022-08-19 10:10:14 回复(0)

Java

小怪ei

假设做出了顾客要求的最大最小值重量的蛋糕c1和蛋糕c2，同时m值增加2
将这两个蛋糕加入做好的蛋糕数组，并将数组排序
如果m>n，说明剩余没做的蛋糕不够两个了，此时有两种情况：

第一：真实的已经做好的蛋糕（不包括c1和c2）中有符合条件的最大和最小的
第二：没有符合条件的最大和最小的

上述情况只需要检查第二项和倒数第二项

检查数组第一项和最后一项（此时是有包括c1和c2的因为有足够的n-m余量用来做出这两个重量的蛋糕）

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.lang.Math;

public class Main{
    private static void service(List<Integer> weight,int n,int m,int a, int b){
        int max = Math.max(a,b);
        int min = Math.min(a,b);
        weight.add(min);
        weight.add(max);
        m+=2;
        weight.sort(Comparator.naturalOrder());
        if(m>n){
            //排除已经存在满足需求的情况，用例： 6 5 2 4     /t     2 4 1 3 4
            if(weight.size()>4&&weight.get(1)==min&&weight.get(weight.size()-1)==max){
                System.out.println("YES");
            }
            else System.out.println("NO");
            return;
        }
        if(weight.get(0)==min&&weight.get(weight.size()-1)==max){
            System.out.println("YES");
            return;
        }
        
        System.out.println("NO");
    }
    
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        List<int[]> datas = new ArrayList<int[]>();
        List<List<Integer>> weights = new ArrayList<List<Integer>>();
        while(scanner.hasNextInt()){
            List<Integer> weight = new ArrayList<Integer>();
            int[] data = new int[4];
            for(int i = 0;i<4;i++){
                data[i] = scanner.nextInt();
            }
            for(int j =0;j<data[1];j++){
                weight.add(scanner.nextInt());
            }
            datas.add(data);
            weights.add(weight);
        }
        for(int k = 0;k<weights.size();k++){
            int n = datas.get(k)[0];
            int m = datas.get(k)[1];
            int a = datas.get(k)[2];
            int b = datas.get(k)[3];
            service(weights.get(k),n,m,a,b);
        }
    }
}

发表于 2022-03-04 21:19:11 回复(0)

Java

郑大涛

import java.util.*;

/**
 * @name  Cake
 * @what
 * @do
 * */
public class Main{

    public static void main(String[] args) {
        Scanner sn = new Scanner(System.in);        
        List<String> list = new ArrayList<>();
        while (sn.hasNext()) {            
            int n = sn.nextInt();
            int m = sn.nextInt();
            int a = sn.nextInt();
            int b = sn.nextInt();
            int min = a<b? a:b;
            int max = a>b? a:b;                
            int[] done = new int[m];
            boolean hasCross = false;
            boolean hasMin = false;
            boolean hasMax = false;
            if (m <= 0) {                  
                if (n >= 2) {
                    System.out.println("YES");                    
                }
                else 
                    System.out.println("NO");                    
            }
            //若m小于0，查看n是否大于等于，补上2个蛋糕
            else {
                   for (int i = 0; i < m; i++) {
                        int x = sn.nextInt();
                        done[i] = x;                     
                    } 
                   //否则，继续接收键盘输入的值，依次赋值给已已烤的面包
                    Arrays.sort(done);
                    //将已烤的面包升序，方便判断面包是否超重或者超轻
                    if (done[0] < min || done[done.length-1] > max) {
                        System.out.println("NO");                    
                    }     
                    //比较第一个和最后一个有不合格则不达标：假设已烤的面包有n个
                    else {
                        //如果没有重量越界的蛋糕，遍历所有蛋糕
                        for (int i = 0; i < m; i++) {                                
                            if (done[i] == min) {
                                hasMin = true;
                            }
                            //如果其中有重量刚好为min的，记录
                            if (done[i] == max) {
                                hasMax = true;                                
                            }                
                            //如果有刚好为max的，记录
                        }                                      
                        if (hasMin==true && hasMax==true) {                        
                            System.out.println("YES");                
                        }
                        //如果都有就YES
                        //否则继续从仓库里找，假设已烤的蛋糕中只有1个达标
                        else if (hasMin==true || hasMax==true) {
                            int delta = n - m;
                            if (delta >= 1) {                            
                                System.out.println("YES");                    
                            }       
                            //只有1个满足时，检查是否有1个以上可以补上
                            else {                            
                                System.out.println("NO");                    
                            }                                                    
                        }    
                        //假设已烤的蛋糕里没有达标的，检查仓库有没有2个或2个以上
                        else if (hasMin==false && hasMax==false) {
                            int delta = n - m;
                            if (delta >= 2) {                            
                                System.out.println("YES");                    
                            }                        
                            else {                            
                                System.out.println("NO");                    
                            }                        
                        }//end else if
                }//end else

            }                                               
        }//end while        
    }//end main
}//end class

发表于 2021-05-20 18:02:14 回复(0)

Java

Chiaa

public class Main{

    private static boolean isReasonable(List<Integer> list, int a, int b){
        return (a == list.get(0) && b == list.get(list.size() - 1)) || (b == list.get(0) && a == list.get(list.size() - 1));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //多组数据
        while(sc.hasNext()){
            //读数据
            int n = sc.nextInt();
            int m = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            int rest = n-m;
            int count = 0;

            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < m; i++){
                list.add(sc.nextInt());
            }

            list.add(a);
            list.add(b);
            //将将已经做好的m个蛋糕和a,b按重量升序排列
            Collections.sort(list);

            //若a,b是最轻最重的蛋糕即合理
            if (isReasonable(list, a, b)){
                //查重（满足最轻或最重的蛋糕被做出的数量）
                for(Integer k : list){
                    if(k.equals(a)){
                        count++;
                    }
                    if(k.equals(b)){
                        count++;
                    }
                }
                //由于列表里加入了a,b，所以count必定会多出2,减去即可
                count -= 2;

                //若（可以现烤的蛋糕）与（满足最轻或最重的蛋糕）之和大于等于2个，即请问小团可以满足他的要求
                if (rest+count >= 2){
                    System.out.println("YES");
                }
                else{
                    System.out.println("NO");
                }
            }
            //若a,b是不是最轻最重的蛋糕即不合理
            else {
                System.out.println("NO");
            }
        }
    }
}

发表于 2021-03-05 23:01:42 回复(0)