首页 > 代码库 > hdu 2141 Can you find it?（二分查找）

hdu 2141 Can you find it?（二分查找）

2024-07-15 12:52:12   221人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2141

题目大意：查找是否又满足条件的x值。

这里简单介绍一个小算法，二分查找。

 1 /* 2  3  x^2+6*x-7==y 4  输入y   求x   精确度为10^-5 5  0=<x<=10000 6  7  */ 8 #include <iostream> 9 #include <cstdio>10 using namespace std;11 int main (void)12 {13     double y;14     while(cin>>y)15     {16         double l,r,x;17         l=0;18         r=10000;//在所给的区间定义边界，一左一右19         while(r-l>0.00001)//精确度的问题20         {21             x=(l+r)/2;//二分来节省计算的次数和时间22             double yy;23             yy=x*x+6*x-7;24             if(yy<y)25                 l=x+0.00001;//选取右半部分区间26             else27                 r=x;28         }29         cout<<l<<endl;30     }31     return 0;32 }
View Code

 以下是对hdu2141的解法；

先把原式化为Ai+Bj = X-Ck.然后在对Ai+Bj 进行二分。

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5  6 __int64 s[250100]; 7  8 int main () 9 {10     int l,n,m,T=1;11     while(scanf("%d%d%d",&l,&n,&m)!=EOF)12     {13         int num=0;14         __int64 a[1000],b[1000],c[1000];15         for (int i=0; i<l; i++)16             scanf("%I64d",&a[i]);17         for (int j=0; j<n; j++)18             scanf("%I64d",&b[j]);19         for (int k=0; k<m; k++)20             scanf("%I64d",&c[k]);21         int t;22         scanf("%d",&t);23         printf("Case %d:\n", T++);24         for (int i=0; i<l; i++)25             for (int j=0; j<n; j++)26                 s[num++]=a[i]+b[j];27         sort(s,s+num);28         //sort(a,a+l);29         //sort(b,b+n);30         sort(c,c+m);31         while (t--)32         {33             __int64 x;34             scanf("%I64d",&x);35             if(x>s[num-1]+c[m-1]||x<s[0]+c[0])36             {37                 printf("NO\n");38                 continue;39             }40             int flag=0;41             __int64 p;42             for (int k=0; k<m; k++)43             {44                 p=x-c[k];45                 int cc;46                 int lz=0,r=num-1;//cout<<r<<endl;47                 while(r>lz)48                 {49                     cc=(r+lz)/2;50                     if (s[cc]<p)51                         lz=cc+1;52                     else if(s[cc]==p)53                     {54                         flag=1;55                         printf ("YES\n");56                         break;57                     }58                     else59                         r=cc-1;60                 }61                 if(flag==1)62                     break;//cout<<k<<endl;63                 if (p==s[r])64                 {65 66                     flag=1;67                     printf("YES\n");68                     break;69                 }70 71             }72             if(flag==0)73                 printf ("NO\n");74 75         }76     }77 }

 


联系
我们