首页 > 试题广场 >

糕点

[编程题]糕点
  • 热度指数:10933 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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

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

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

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

数据范围:
进阶:时间复杂度,空间复杂度

输入描述:

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

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

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



输出描述:

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

示例1

输入

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

备注:

对于40%的数据,

对于100%的数据,,蛋糕重量不会超过1000

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main{

    public static void  main(String args[]){
        int[] list1 = new int[4];//定义数组

                //获取第一组数据
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] split = s.split(" ");
        for(int i=0;i<split.length;i++){
           list1[i] = Integer.valueOf(split[i]);
        }

                
        boolean res = false;
        int n = list1[0],m=list1[1],a=list1[2],b=list1[3];

        //将a b 排个序 因为有时候会输入4 2
        if(a>b){
            int tmp = a;
            a = b;
            b=tmp;
        }

                //再读取第2组数据 并利用现有的方法排个序
        ArrayList<Integer> array = new ArrayList<Integer>();
        String s2 = sc.nextLine();
        String[] split2 = s2.split(" ");
        for(int i=0;i<m;i++){
            array.add(Integer.valueOf(split2[i]));
        }
        Collections.sort(array);

                
        int temp = 0;
        if(array.contains(a))temp++;
        if(array.contains(b))temp++;
                //如果已经存在 a b了肯定是true
        if(temp == 2){
            res= true;
        } else{
            // 最小不能小过a  最大不能大过 b 因为array已经排过序了可以直接取头尾
            if(array.get(m-1) > b  || array.get(0) < a) {res = false;}
            else {
                if(n-m >= 2){ res= true;} //如果还要做的蛋糕超过2个,就true
                else{ 
                                    res=false;
                                }
            }
        }

        if(res){

            System.out.println("YES");
        }else {

            System.out.println("NO");
        }
    }
}

发表于 2021-04-26 15:23:45 回复(0)
// 参考了别人代码,修改了一下,但是只有80%,希望指教一下
var start = readline();
while (start) {
    var [n, m, a, b] = start.split(" ");
    var dones = readline().split(" ");
    dones = dones.sort((x, y) => x - y);
    var left = n - m;
    var muti = 0;
    for (var i = 0; i < dones.length; i++) {
        if (dones[i] == a) {
            muti++;
        }
        if (dones[i] == b) {
            muti++;
        }
    }
    if (left == 0) {
        if (dones.includes(a) && dones.includes(b)) {
            print("YES");
        } else {
            print("NO");
        }
    }
    if (left == 1) {
        if (muti > 0) {
            print("YES");
        } else {
            print("NO");
        }
    }
    if (left >= 2) {
        if (muti > 0) {
            print("YES");
        } else {
            if (left > dones.length) {
                print("YES");
            } else if (a < dones[0] && b > dones[dones.length - 1]) {
                print("YES");
            } else {
                print("NO");
            }
        }
    }
    start = readline();
}

编辑于 2021-03-15 20:12:30 回复(1)
while True:
    try:
        s1 = list(map(int,input().split()))
        s2 = list(map(int,input().split()))
        n, m, a, b = s1
        s2.sort()
        if s2[0]<a and s2[0]<b&nbs***bsp;s2[-1]>a and s2[-1]>b&nbs***bsp;a not in s2 and b not in s2 and n-m<2:
            print ('NO')
        else:
            print ('YES')
    except:
        break

发表于 2021-03-17 22:07:48 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//题目中貌似默认n >= 2,m <= n;

void solution()
{
    int n = 0, m = 0, a = 0, b = 0;
    while (cin >> n >> m >> a >> b)
    {
        if (a < b) //输入没有确定出a和b的大小,需要自己确定
        {
            int temp = a;
            a = b;
            b = temp;
        }
        vector<int> nums(m, 0);
        for (int i = 0; i < m; ++i) //输入已经烤好的面包
            cin >> nums[i];
        sort(nums.begin(), nums.end()); //排序
        if (nums[0] < b || nums.back() > a) //已经烤好的重量有更轻的或更重的
        {
            cout << "NO\n";
            continue;
        }
        //进行到这一行,说明已经烤好的面包的重量在b和a之间
        //对数组进行改造,相当于再烤一个最轻的和一个最重的
        if (nums[0] != b)
            nums.insert(nums.begin(), b); 
        if (nums.back() != a)
            nums.insert(nums.end(), a);
        //数量超了,就不行
        if (nums.size() > n)
            cout << "NO\n";
        else cout << "YES\n";
        
        //假如最轻的和最重的一样,设为2,且当前烤好的只有1个,重量也为2,上面的代码能行吗?可以的,这里默认n >= 2;
        //这样当代码进行到第30行,烤好的这个面包可以满足最重或最轻的其中一个,再烤一个即可,在最后判断条件里,可以通过
    }
}

int main()
{
    solution();
    return 0;
}

发表于 2021-08-15 10:29:16 回复(1)

对于这种特判条件特别多的问题,我们千万别慌,慢慢想,我就做了40分钟。
我们要尽量保证每种情况都能顾忌到,下面参考我的临场笔记吧。

/*
20:46
总共n个,已有m个,a最重b最轻
已有的蛋糕数量已知
首先,要买最重和最轻。如果a,b在已有蛋糕重量中不是最重和最轻,则无法满足
设还可以烤k个蛋糕,k=n-m.

如果n < 2,pass,no

如果n >= 2:
m == 0, 则k = 2,yes
m == 1:
如果这个蛋糕=a或=b, k >= 1,yes
如果这个蛋糕b<蛋糕<a,我们需要自己做a,b,此时如果k>=2,yes
m >= 2:
如果所有蛋糕都在[b,a],且有a也有b,yes
如果所有蛋糕都在(b,a),我们要自己做a,b. 若k>=2,yes
以上,把n和m所有可能的情况都考虑到了,再加上a和b比较大小这种坑b条件
*/






#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m, a, b;
    while(~scanf("%d%d%d%d",&n,&m,&a,&b))
    {
        bool f = 0;
        int k = n-m;
        if(a < b) swap(a,b); //**条件
        if(n >= 2)
        {
            if(m == 0) f = 1;
            else if(m == 1)
            {
                int x;
                scanf("%d",&x);
                if((x == a || x == b) && k >= 1) f = 1;
                if(x > b && x < a && k >= 2) f = 1;
            }
            else
            {
                int Max, Min;
                for(int i = 0;i < m;i++)
                {
                    int x;
                    scanf("%d",&x);
                    if(i == 0) Min = x, Max = x;
                    Min = min(Min,x);
                    Max = max(Max,x);
                }
                if(Min == b && Max == a) f = 1;
                if(Min >= b && Max <= a && k >= 2) f = 1;
            }
        }
        if(f) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
发表于 2021-03-15 23:05:01 回复(3)
模拟一下,在保证a<b的情况下,有如下几种情况:
(1) 已经烤好的蛋糕中,重量最小的比a轻,或者重量最大的比b重,肯定无法满足要求。
(2) 已经烤好的蛋糕重量都在区间[a,b]中
    i) 已经有a和b两个重量,可以满足要求。
    ii) 已经有a或b之中的一个重量,并且还能现烤的蛋糕数不少于1,那就肯定还能够烤一个需要的重量;否则不能满足要求。
    iii) 需要的两个重量都没有,并且能还能现烤的蛋糕数不少于2,那就肯定可以把需要的两个重量都烤了;否则不能满足要求。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        String[] params;
        while((line = br.readLine()) != null) {
            params = line.trim().split(" ");
            int n = Integer.parseInt(params[0]);
            int m = Integer.parseInt(params[1]);
            int a = Integer.parseInt(params[2]);
            int b = Integer.parseInt(params[3]);
            params = br.readLine().trim().split(" ");
            int[] weight = new int[m];
            HashSet<Integer> set = new HashSet<>();      // 保存现有蛋糕的重量
            for(int i = 0; i < m; i++) {
                weight[i] = Integer.parseInt(params[i]);
                set.add(weight[i]);
            }
            Arrays.sort(weight);
            // 保证a<b
            if(a > b){
                int temp = a;
                a = b;
                b = temp;
            }
            if(weight[0] < a || weight[m - 1] > b){
                // 现有蛋糕中,重量最小的小于a,最大的大于b,肯定完成不了需求
                System.out.println("NO");
            }else{
                if(set.contains(a) && set.contains(b))   // 如果现有蛋糕中已经包含了a和b,就没问题
                    System.out.println("YES");
                else{
                    if(set.contains(a) || set.contains(b)){
                        // 如果只包含a或b,检查一下n-m是否大于等于1,即还有一个重量需要现烤
                        System.out.println(n - m >= 1 && weight[m - 1] <= b? "YES": "NO");
                    }else{
                        // 否则需要检查n-m是否大于等于2,即两个重量都需要现烤
                        System.out.println(n - m >= 2? "YES": "NO");
                    }
                }
            }
        }
    }
}


编辑于 2021-03-06 18:21:31 回复(1)
这道题我认为不需要用任何数据结构,即使用O(1)空间复杂度就能解决问题,只需要运用数学的分类讨论思想,对以下三种情况分别讨论即可。

1.先记录已经做好的蛋糕里面最轻的和最重的,分别记为minSize和maxSize
2.分以下三大类讨论
  ①如果n-m>=2,即还有2个以上的蛋糕可以新制作
        //如果minSize>=a,maxSize<=b,则返回Yes
        //否则返回No
  ②如果n-m==1,即只有1个蛋糕可以新制作
        这时判断minSize和maxSize里面是否有一个等于a或者b
    //如果没有:那么返回NO
    //如果有两个:返回Yes
    //如果有一个:那就判断是不是等于a或者b,进而将缺少的重量与minSize和maxSize进行对比
  ③如果n-m==0,即没有蛋糕可以新制作了,这时就看minSize和maxSize是否分别等于a,b了


import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
        int n=sc.nextInt();
        int m=sc.nextInt();
        int a=sc.nextInt();
        int b=sc.nextInt();
        //保证a更轻,b更重
        if(a>b){
            int temp=a;
            a=b;
            b=temp;
        }
        boolean flag=false;
	    int cake=0;
        int minSize=1000;
        int maxSize=0;
        for(int i=0;i<m;i++){
            cake=sc.nextInt();
	    minSize=Math.min(minSize,cake);
	    maxSize=Math.max(maxSize,cake);
        }
                //分类讨论
        if(n-m>=2){
            if(minSize>=a&&maxSize<=b)flag=true;
        }else{
            if(n-m==1){
                if(minSize==a&&maxSize==b)flag=true;
                else if(minSize==a){
                    if(maxSize<b)flag=true;
                }
                else if(minSize==b){
                    if(minSize>a)flag=true;
                }
            }else{
                if(minSize==a&&maxSize==b)flag=true;
            }
        }
        if(flag==true)System.out.println("YES");
            else System.out.println("NO");
        }
    }
}


编辑于 2022-03-20 13:46:27 回复(2)
while True:
    try:
        n,m,a,b= map(int,input().strip().split())
        y = list(map(int, input().strip().split()))
        y.sort()
        if max(y)== max(a,b) and min(y)== min(a,b):
            print("YES")
        elif max(y) != max(a,b) and min(y)== min(a,b):
            if n-m>=1 and max(y) < max(a,b):
                print("YES")
            else:
                print("NO")
        elif max(y) == max(a,b) and min(y)!= min(a,b):
            if n-m>=1 and min(y)> min(a,b):
                print("YES")
            else:
                print("NO")
        elif max(y)!= max(a,b) and min(y)!= min(a,b):
            if n-m>=2 and max(y) < max(a,b) and min(y)> min(a,b):
                print("YES")
            else:
                print("NO")
    except:break

无脑暴力列举情况
发表于 2022-08-27 14:43:26 回复(0)
判断已烤好的最大最小值和a, b的大小关系
#include "bits/stdc++.h"
using namespace std;
 
bool f(int n, int m, int a, int b, vector<int>& nums){
    if (a > b) swap(a,b);
    int max_num = *max_element(nums.begin(), nums.end());
    int min_num = *min_element(nums.begin(), nums.end());
    if (n - m>=2){
        if (a <= min_num && b >= max_num) return true;
    }else{
        if (a == min_num && b >= max_num || a <= min_num && b==max_num) return true;
    }
     return false;
}
 
int main(){
    int n, m, a,b;
    while(cin>>n>>m>>a>>b){
        vector<int> nums(m);
        for(int i=0; i<m; i++)   cin>>nums[i];
        if (f(n,m,a,b,nums))
            cout << "YES"<<'\n';
        else
            cout << "NO"<<'\n';
    }
    return 0;
}


发表于 2022-05-03 16:14:52 回复(0)
while True:
    try:
        n,m,a,b=map(int,input().split())
        # n:总共蛋糕个数, m:已做好蛋糕数量
        # a, b: 想购买的蛋糕数量
        li = list(map(int,input().split())) # 烤好蛋糕的重量

        if max(li)>max(a,b) or min(li)<min(a,b):
            print('NO')
            pass
        elif n-m >= 2:
            print('YES')
        elif n-m == 1:
            if max(li)==max(a,b) or min(li)==min(a,b):
                print('YES')
            else:
                print('NO')
        elif n-m == 0:
            if max(li)==max(a,b) and min(li)==min(a,b):
                print('YES')
            else:
                print('NO')
    except:
        break

小白一个,估计有很多冗余语句。。。
编辑于 2021-10-30 22:18:31 回复(0)
nums = input()
while True:
    n,m,a,b = map(int, nums.split())
    weight = list(map(int, input().split()))
    minimum = min(weight)
    maximum = max(weight)
    if a > b:
        tmp = a
        a = b
        b = tmp
    answer = "YES"
    if minimum < a:
        answer = "NO"
    else:
        if maximum > b:
            answer = "NO"
        else:
            if n - m == 1:
                if minimum > a and maximum < b:
                    answer = "NO"
            elif n - m == 0:
                if minimum >a&nbs***bsp;maximum <b:
                    answer = "NO"
    print(answer)
    try:
        nums = input()
    except:
        break


发表于 2021-03-03 18:29:58 回复(0)
#include <bits/stdc++.h>
using namespace std;

int n,m,a,b;
int maxN = 0;
int minN = INT32_MAX;

bool check(vector<int> vec){
    if (a < maxN || b > minN) return false;
    if ((n - m) >= 2) return true;

    if (a == maxN && b == minN) return true;
    else if ((a == maxN || b == minN) && (n - m) >= 1) return true;
    return false; 
}

int main() {
    while (cin >> n >> m >> a >> b) {
        vector<int> vec(m);
        maxN = 0;
        minN = INT32_MAX;
        for (int i = 0; i < m; i++) {
            cin >> vec[i];
            if (vec[i] > maxN) maxN = vec[i];
            if (vec[i] < minN) minN = vec[i]; 
        }
        if (a < b) swap(a,b);
        if(check(vec)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

发表于 2024-03-08 00:32:46 回复(0)
#include <iostream>
using namespace std;
#include <vector>
#include<algorithm>

int main() {
int n,m,a,b;
while(cin>>n>>m>>a>>b)
{vector<int> height(m,0);
for(int i=0;i<m;i++){
    cin>>height[i];
}
//令a为客户期望最小重量,b为客户期望最大重量
if(a>b){
    int temp=a;
    a=b;
    b=temp;
}
auto iter1=find(height.begin(),height.end(),a);
if(iter1==height.end()) height.push_back(a);
auto iter2=find(height.begin(),height.end(),b);
if(iter2==height.end()) height.push_back(b);
sort(height.begin(),height.end());
if(a!=height[0]||b!=height[height.size()-1]||height.size()>n) {
    cout<<"NO"<<endl;
    }
else {cout<<"YES"<<endl;}
}
return 0;
    

}
只能说多练练ACM模式
发表于 2023-03-24 20:30:32 回复(0)
while True:
    try:
        n,m,a,b = map(int, input().split())
        cake = list(map(int, input().split()))
        if n-m >= 2:
            if min(a,b)<=min(cake) and max(a,b)>=max(cake):
                print('YES')
            else:
                print('NO')
        elif n-m == 1:
            if a in cake&nbs***bsp;b in cake:
                if min(a,b)<=min(cake) and max(a,b)>=max(cake):
                    print('YES')
                else:
                    print('NO')
            else:
                print('NO')
        else:
            if a in cake and b in cake and min(a,b)<=min(cake) and max(a,b)>=max(cake):
                print('YES')
            else:
                print('NO')
    except:
        break
一种比较暴力的分类讨论
发表于 2023-03-06 00:37:25 回复(0)
import java.util.*;

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 ((max == b && min == a)||(min > a && max < b && n - m >= 2 )|| (((max == b &&  min > a )||(min == a && max < b)) && n - m >= 1)){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }

        }
    }
}
发表于 2022-09-12 13:55:15 回复(0)

if __name__ == '__main__': while (True): try:
            varibles = input()
            m_weight = input()
            varibles = varibles.split(sep=' ')
            n = int(varibles[0])
            m = int(varibles[1])
            a = int(varibles[2])
            b = int(varibles[3]) if a > b:
                temp = a
                a = b
                b = temp
            m_weight = m_weight.split(sep=' ')
            m_weight = list(map(eval, m_weight)) if (n - m) >= 2: if a > min(m_weight): print("NO") elif b < max(m_weight): print("NO") else: print("YES") elif (n - m) == 1: if (a == min(m_weight) and b < max(m_weight)) or (b == max(m_weight) and a > min(m_weight)): print("YES") else: print("NO") else: if a == min(m_weight) and b == max(m_weight): print("YES") else: print("NO") except: break         

发表于 2022-08-27 12:15:29 回复(0)
我是不是没有循环输入所以导致答案错误?? 浪费我30分钟的调试时间。。
package main
 
import "fmt"
 
func main() {
    n, m := 0, 0
    a, b := 0, 0
    fmt.Scan(&n, &m, &a, &b)
    if a > b { // 永远保证a比b小
        a, b = b, a
    }
    cakes := make([]int, m)
    for i := 0; i < m; i++ {
        fmt.Scan(&cakes[i])
    }
    QuickSort(&cakes, 0, len(cakes)-1)
    if cakes[0] < a || cakes[len(cakes)-1] > b {
        fmt.Println("NO")
        return
    }
 
    canMake := n - m
 
    if canMake == 0 {
        if n <= 1 {
            fmt.Println("NO")
            return
        }
        if cakes[0] == a && cakes[len(cakes)-1] == b {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
        return
    }
    if canMake == 1 {
        if (a == cakes[0] && b > cakes[len(cakes)-1]) || (a < cakes[0] && b == cakes[len(cakes)-1]) {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
        return
    }
 
    if canMake >= 2 {
        if cakes[0] >= a && cakes[len(cakes)-1] <= b {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
        return
    }
 
}
 
func QuickSort(arr *[]int, left, right int) {
    if left < right {
        cursor := (*arr)[left]
        l := left
        r := right
        for l < r {
            for l < r && (*arr)[r] > cursor {
                r--
            }
            if l < r {
                (*arr)[l] = (*arr)[r]
                l++
            }
            for l < r && (*arr)[l] < cursor {
                l++
            }
            if l < r {
                (*arr)[r] = (*arr)[l]
                r--
            }
        }
        (*arr)[l] = cursor
        QuickSort(arr, left, l-1)
        QuickSort(arr, l+1, right)
    }
}

发表于 2022-08-25 00:03:34 回复(0)
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)
while True:
    try:
        n, m, a, b = list(map(int,input().split()))
        s2 = list(map(int,input().split()))
        mi = min(s2)
        ma = max(s2)
        if(b<a):
            a,b=b,a
        if mi<a&nbs***bsp;ma>b&nbs***bsp;n-m<((mi!=a)+(ma!=b)):
            print('NO')
        else:
            print('YES')
    except:
        break

发表于 2022-08-19 09:39:43 回复(0)
// 第一步:检查已经做好的面包是否满足[a, b]范围 -> YES/No
// 第二步:检查已经做好的面包中含有a和b的情况,总共4种:含a含b,含a不含b,含b不含a,都不含
// 第三步:检查剩余可做面包n-m是否能做出上面四种的条件 -> Yes/No
let line
while(line = readline()) {
    const [n, m, a, b] = line.split(' ').map(Number) // n总共可以做的面包,m已经做了的面包,所有面包重量需要满足[a, b]
    const weights = readline().split(' ').map(Number)  // weights.length = m
    // 第一步
    const res = weights.every(v => (v <= b && v >= a) || (v <= a && v >= b))
    if(!res) {
        console.log('NO')
        continue
    }
    // 第二步
    let count = 0
    if(!weights.includes(a)) {
        count++
    }
    if(!weights.includes(b)) {
        count++
    }
    // 第三步
    if((n - m) >= count) {
        console.log('YES')
    } else {
        console.log('NO')
    }
}

发表于 2022-06-10 16:28:56 回复(0)