首页 > 分享 > HDU 2141(二分算法)

HDU 2141(二分算法)

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

Description

超市一共有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

刚做这道题的时候直接用了3层for循环WA了，下去后看了下博客，发现用的是二分，然后过了，二分这个算法挺简单的，但是关键点在于是否能够灵活的运用。这道题思路就是先把前两排的合并，合并之后与第三排相加判断是否等于你输入的数，同时相加的时候用了二分的思想。

#include <stdio.h> #include <string.h> #include <algorithm> #include<iostream> using namespace std; int main() { int l,m,n,u=1; while(scanf("%d%d%d",&l,&m,&n)!=EOF) { int x[l+6],y[m+5],z[n+6]; long long v[l*m+5]; for(int a=1;a<=l;a++) scanf("%d",&x[a]); for(int a=1;a<=m;a++) scanf("%d",&y[a]); for(int a=1;a<=n;a++) scanf("%d",&z[a]); int k=1; for(int i=1;i<=l;i++) //合并 { for(int j=1;j<=m;j++) { v[k++]=x[i]+y[j]; } } sort(v+1,v+1+k); int q; scanf("%d",&q); printf("Case %d:n",u++); while(q--) { int p,g; g=0; scanf("%d",&p); for(int i=1;i<=n;i++) { int start=1,endd=k-1; while(start<=endd) //二分 { int middle=(start+endd)/2; if(z[i]+v[middle]==p) { g=1;break; } else if(v[middle]+z[i]<p) { start=middle+1; } else { endd=middle-1; } } if(g==1) { break; } } if(g==1) { printf("YESn"); } else { printf("NOn"); } } } return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970