湖南科大水题反思

给定一个集合，查找元素是否在集合中出现。

每个测试用例由多行组成，第一行是两个整数n和m，这2个数的取值在1到3 000 000之间。

自第二行起一共有n+m个整数，其中前面n个整数代表集合的元素，随后的m个整数是待查询的数。n+m个整数的取值在范围1到10 000 000之间。

对于每个待查询的数，如果在集合中则输出yes,否则输出no.

5 345 56 23 6 56633 66 63 22934 235 555555 230 0

no

no

yes

yes

no

本来用set 直接过了 但是stl耗时   老师加强数据后就超时了

然后就想到用二分法    把二分函数写到了主函数外  结果依旧超时

郁闷    但是 把二分函数写进了主函数以后就过了

这个题给我的警示就是  以后 尽量少调用函数  因为调用也耗时间

set超时版

#include<stdio.h> #include<set> using namespace std; int main() {     int n,m,i,j;     while(scanf("%d %d",&n,&m)!=EOF)     {         if(!n&&!m) break;         int num;         set<int>ss;         set<int>::iterator it;         for(i=0;i<n;i++)         {             scanf("%d",&num);             ss.insert(num);         }         for(i=0;i<m;i++)         {             scanf("%d",&num);             it=ss.find(num);             if(it!=ss.end())                 printf("yes\n");             else printf("no\n");           }     }     return 0; } 

//ac
#include<stdio.h> #include<algorithm> using namespace std; int a[3000000+100]; int n; int main() {     int m,i,j,num,left,right,mid,flag;        while(scanf("%d %d",&n,&m)!=EOF)        {            if(!n&&!m) break;            for(i=1;i<=n;i++)                scanf("%d",&a[i]);            sort(a+1,a+1+n);            for(i=0;i<m;i++)            {                scanf("%d",&num);                left=1;right=n;                flag=0;mid;                while(left<=right)                {                    mid=(right+left)/2;                    if(a[mid]>num) right=mid-1;                    else if(a[mid]<num) left=mid+1;                    else if(a[mid]==num) {flag=1;break;}                }                if(flag)                    printf("yes\n");                else printf("no\n");            }        }        return 0; }