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

题目链接：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             else
27                 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:
", 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
");
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
");
56                         break;
57                     }
58                     else
59                         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
");
68                     break;
69                 }
70 
71             }
72             if(flag==0)
73                 printf ("NO
");
74 
75         }
76     }
77 }