红包购物挑战

• 花匠小妙招
• 2025-05-15 17:49

超市一共有ABC三个货架, 每个货架上都有若干种商品(每种有无限多个), 比如A货架上的第i种商品的价格是Ai元.

白学姐发了K个红包, 但是ta要求对于每个红包, 从三个货架上各拿一个商品, 把红包里的钱恰好花光, 这可能吗?

Input

每个输入包含多组样例.
每组样例的第一行有三个整数L, N, M(1<=L, N, M<=500), 表示A, B, C三个货架上分别有L, N, M种商品
接下来三行, 每行分别有L, N, M个数字, 代表A, B, C三个货架上每种商品的价格.
第五行有一个整数K表示有K个红包, 1<=K<=1000
接下来K行每行有一个数代表一个红包内的钱数

所有整数均在32位整型的范围内

Output

对于第i组样例输出一行Case i:
接下来K行对于每个红包的期望输出一行 如果可以满足则输出 YES 否则输出 NO

Sample Input

3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10

Sample Output

Case 1:
NO
YES
NO

题意：

给三个长度分别为L,N,M数数组，从每个数组里面取出一个数相加，如果存在和为K的数，就输出YES，反之，就输出NO

题解：

话不多说，先给代码：

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

using namespace std;

int main()

{

int a[501],b[501],c[501];

int L,N,M;

scanf("%d%d%d",&L,&N,&M);

for(int i=1;i<=L;++i)

scanf("%d",&a[i]);

for(int i=1;i<=N;++i)

scanf("%d",&b[i]);

for(int i=1;i<=M;++i)

scanf("%d",&c[i]);

int num;

cin>>num;

while(num)

{

int number;

int judgee=0;

cin>>number;

for(int i=1;i<=L;++i)

for(int j=1;j<=N;++j)

{

for(int k=1;k<=M;++k)

{

if(a[i]+b[j]+c[k]==number)

{

judgee=1;

}

}

}

if(judgee==1)

printf("YESn");

else

printf("NOn");

}

return 0;

}

上面的代码可以通过样例，但是时间超限，因为三层for循环，算一下就是500*500*500.

那，该怎么做呢？

可以使用二分的方法进行优化，这样时间复杂度就降下来了，那么就讨论一下怎么二分。

首先，一共有三层for循环，那么这三层for循环就可以作为我们优化的突破口

我们可以把前两层for循环相加得到的数据存入一个数组，然后遍历第三层for循环的数据，在每一次遍历的时候二分前面的那个数组。

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<iostream>

#include<queue>

#include<string>

using namespace std;

int a[505],b[505],c[505];

int num[251000];

int main()

{

int L,N,M,v=1;

while(~scanf("%d%d%d",&L,&N,&M))

{

printf("Case %d:n",v++);

int cnt=0;

for(int i=0;i<L;++i)

scanf("%d",&a[i]);

for(int j=0;j<N;++j)

scanf("%d",&b[j]);

for(int k=0;k<M;++k)

scanf("%d",&c[k]);

for(int i=0;i<L;++i)

{

for(int j=0;j<N;++j)

{

num[cnt++]=a[i]+b[j];

}

}

sort(num,num+cnt);

int m;

cin>>m;

while(m--)

{

int judge;

int number;

cin>>number;

for(int i=0;i<M;++i)

{

judge=1;

int findd=number-c[i];

int left=1,right=cnt;

int mid=(left+right)/2;

while(left<right)

{

if(num[mid]<findd) left=mid+1;

else if(num[mid]>findd) right=mid-1;

else

break;

mid=(left+right)/2;

}

if(num[mid]==findd)

{

judge=0;

break;

}

}

if(judge==0)

printf("YESn");

else

printf("NOn");

}

}

return 0;

}

相关知识

红包购物挑战
红包榨果汁红包版
红包版消除游戏大全
锦上添花红包版赚钱下载安装
热带水果园喜得红包
锦上添花红包版下载
美味香蕉园红包版游戏
爱上鲜花红包版游戏下载
解压爱消消赚红包版下载
花语世界游戏红包版下载

网址: 红包购物挑战 https://m.huajiangbk.com/newsview1965642.html

上一篇: 蓝桥杯国赛每日一题：巧克力（贪心

下一篇: 鲜果出口挑起致富“金扁担”