1223: 上海红茶馆 ~ Chinese Tea
时间限制: 1 Sec题目描述
你现在正在经营一家红茶馆, 而且这里有各种各样的红茶, 你现在把这些红茶分成了N个等级, 每个等级的茶有一个品质Q。
现在每一个来的客人都会要求一个品质为S的茶, 你需要迅速的回答他是否有。
输入
第一行两个数N,M。
下面一行N个数, 分别表示每个等级的茶的品质Q。
下面一行M个数, 分别表示询问的品质S。
输出
输出一行M个字符, 表示回答是否。 Y表示有, N表示没有。
样例输入
5 5 1 3 4 6 8 1 2 3 4 5
样例输出
YNYYN
提示
30%:N,M<5000
100%:N,M<200000
【题解】
本题有多种解法:
首先我想到自己开一个bool数组来哈希一下,发现哈希的不够优秀,过了85%。
然后我就想到了排序+二分,这样就可以过了,1800ms
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 int n,m,a[200001]; 5 inline int getint() { 6 int x=0,f=1; char c; 7 c=getchar(); 8 while(c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} 9 while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} 10 return x*f; 11 } 12 int main() { 13 n=getint();m=getint(); 14 for (int i=1;i<=n;++i)a[i]=getint(); 15 sort(a+1,a+n+1); 16 bool f=0; 17 for (int i=1;i<=m;++i,f=0) { 18 int x,l=1,r=n; x=getint(); 19 while(l<=r) { //cout<<l<<' '<<r<<endl; 20 if(a[l]==x||a[r]==x) {f=1; break;} 21 int mid=(l+r)>>1; 22 if(a[mid]==x) {f=1;break;} 23 if(x<a[mid]) r=mid-1; 24 else if(x>a[mid]) l=mid+1; 25 } 26 if(f) printf("Y"); 27 else printf("N"); 28 } 29 printf(" "); 30 return 0; 31 }
然后我就发现了,可以用STL的map!就又写了一个简单多的程序,AC了,4000ms
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<stdio.h> 2 #include<map> 3 #include<algorithm> 4 using namespace std; 5 int n,m; 6 map<int,bool> a; 7 inline int getint() { 8 int x=0,f=1; char c; 9 c=getchar(); 10 while(c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} 11 while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();} 12 return x*f; 13 } 14 int main() { 15 n=getint();m=getint(); 16 for (int i=1;i<=n;++i) { 17 int x;x=getint(); 18 a[x]=1; 19 } 20 21 bool f=0; 22 for (int i=1;i<=m;++i,f=0) { 23 int x,l=1,r=n; x=getint(); 24 if(a[x]==1) printf("Y"); 25 else printf("N"); 26 } 27 printf(" "); 28 return 0; 29 }
还是二分快啊TAT我的哈希还是炸啊QAQQQQQ