小团的蛋糕铺长期霸占着美团APP中“蛋糕奶茶”栏目的首位,因此总会吸引各路食客前来探店。
小团一天最多可以烤n个蛋糕,每个蛋糕有一个正整数的重量。
早上,糕点铺已经做好了m个蛋糕。
现在,有一个顾客要来买两个蛋糕,他希望买这一天糕点铺烤好的最重的和最轻的蛋糕,并且希望这两个蛋糕的重量恰好为a和b。剩余的n-m个蛋糕可以现烤,请问小团能否满足他的要求?
数据范围:,
进阶:时间复杂度,空间复杂度
小团的蛋糕铺长期霸占着美团APP中“蛋糕奶茶”栏目的首位,因此总会吸引各路食客前来探店。
小团一天最多可以烤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
对于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"); } } }
// 参考了别人代码,修改了一下,但是只有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(); }
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
#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; }
对于这种特判条件特别多的问题,我们千万别慌,慢慢想,我就做了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; }
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"); } } } } } }
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"); } } }
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
#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; }
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
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
#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模式
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一种比较暴力的分类讨论
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
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) } }
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"); } } }
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
// 第一步:检查已经做好的面包是否满足[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') } }