小团的蛋糕铺长期霸占着美团APP中“蛋糕奶茶”栏目的首位,因此总会吸引各路食客前来探店。
小团一天最多可以烤n个蛋糕,每个蛋糕有一个正整数的重量。
早上,糕点铺已经做好了m个蛋糕。
现在,有一个顾客要来买两个蛋糕,他希望买这一天糕点铺烤好的最重的和最轻的蛋糕,并且希望这两个蛋糕的重量恰好为a和b。剩余的n-m个蛋糕可以现烤,请问小团能否满足他的要求?
数据范围:
,
进阶:时间复杂度
,空间复杂度%5C)
小团的蛋糕铺长期霸占着美团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')
}
}