7.30二分及三分（组队的）

Problem A POJ 1905  Expanding Rods （二分法）

题目大意就是说有一根细丝，在受热后会膨胀产生形变，变为一个圆弧，给出圆弧变化前后的长度，求这根细丝在水平上升高了多少

解题过程：由于题目呢给定了说形变不会是细丝变为超过一个半圆的形状，所以我们就可以对形变的高度二分假设升高了x，那么设圆的半径为R，就存在公式

                                R^2 - (R-x)^2 = (L/2)^2       其中L是细丝变化前的长度

解出来                       R = x/2 + (L*L)/(8*x);

然后可以求出圆心角      Sita = 2 * asin((L/2) / R);

在比较R*Sita与L1(形变后的长度)   其实这里我也没有证明它在0~（L/2）之间是严格递增或是严格递减的，反而证明出了在这个区间他是有增有减的，所以我很郁闷，暂且只能放在这里了，代码是直接二分给出的，我三分求最大值后，再在最小到最大值之间二分反而错了，实在是无解了，网大神指点

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 const double eps1 = 1e-4;
 5 double L,L1,n,C;
 6 
 7 int main()
 8 {
 9     while(~scanf("%lf%lf%lf", &L, &n, &C) && (L!=-1))
10     {
11         if(!L || !n || !C) {printf("0.000
"); continue;}
12         L1 = L * (1 + n * C);
13         double l = 0, r = L/2,mid,R,Sita;
14         while(r-l>eps1)
15         {
16             mid = (l+r)/2;
17             R = mid/2 + L*L/mid/8;
18             Sita = 2 * asin(L/2/R);
19             if(Sita * R > L1) r = mid;
20             else l = mid;
21         }
22         printf("%.3lf
", mid);
23     }
24     return 0;
25 }

Problem B POJ 2002 Squares

还没有搞出

Problem C POJ 2456  Aggressive cows

题目大意是说给出n个牛棚和m头牛，目标是将m头牛放进n个牛棚中去，且要让他们两两之间的距离尽量大，求这时最小的两个有牛的牛棚之间的距离

目标是要让有牛的牛棚之间的距离尽量大，且那时距离最小的两个牛棚之间的距离，那我们就可以直接二分这个最小距离，如果当前这个最小距离可以满足把所有的牛全部放进去，而且还有多的牛棚，那就二分他与最大值之间的距离，否则二分他与最小值之间的中点

以下是章爷的代码

 1         #include <iostream>
 2         #include <cstdio>
 3         #include <cstring>
 4         #include <queue>
 5         #include <algorithm>
 6         #include <cmath>
 7         #include <stack>
 8         #define LL long long
 9         using namespace std;
10         const int inf=0x3f3f3f3f;
11         const int maxn=100000+10;
12         int x[maxn],c,n;
13         int judge(int val)
14         {
15             int i,sum=1,cur=0;
16             for(i=1;i<n;i++)
17             {
18                 if(sum==c) break;
19                 if(cur+x[i]>=val)
20                 {
21                     sum++;
22                     cur=0;
23                 }
24                 else cur+=x[i];
25             }
26             if(sum==c) return 1;
27             else return 0;
28         }
29         int main()
30         {
31             cin>>n>>c;
32             int i;
33             for(i=0;i<n;i++) scanf("%d",&x[i]);
34             sort(x,x+n);
35             for(i=n-1;i>=1;i--) x[i]=x[i]-x[i-1];
36             int low=0,high=1000000001,mid;
37             while(high>low)
38             {
39                 mid=low+(high-low)/2;
40                 if(judge(mid)) low=mid+1;
41                 else high=mid;
42             }
43             printf("%d
",low-1);
44             return 0;
45         }

Problem D HDU 2141 Can you find it?

题目是说给出一系列的A，B和C，以及一些和sum，要你对每一个sum从A，B和C数组中分别找出一个使他们的和为当前这个sum，最开始做的时候哦直接枚举A和B，然后用sum减去每一个C，再二分这个数组，居然发现超时了。

仔细一分析，有1000个sum，500个A，500个B，再加上二分sum-C，时间复杂度就是O（1000 * 500 * 500 * log500）,明显超时了，后来章爷突发灵感，吧A+B保存起来，再对每一个sum-C数组，二分A+B这样复杂度就是O（1000 * 500 * log250000）,可以过了，挂拉呱啦敲完了，过了！！！膜拜章爷啊啊啊~~~

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int a[505],b[505],c[505],ab[250005];
 6 int A,B,C,AB,X,S;
 7 
 8 int find_AB(int sum)
 9 {
10     int l=0,r=AB-1;
11     while(l<=r)
12     {
13         int x=(l+r)>>1;
14         if(sum == ab[x]) return 1;
15         else if(sum < ab[x]) r = x-1;
16         else l=x+1;
17     }
18     return 0;
19 }
20 
21 
22 int main()
23 {
24     int Case=1;
25     while(~scanf("%d%d%d",&A, &B, &C))
26     {
27         for(int i=0;i<A;i++)
28         {
29             scanf("%d", &a[i]);
30         }
31         AB = 0;
32         for(int i=0;i<B;i++)
33         {
34             scanf("%d", &b[i]);
35             for(int j=0;j<A;j++)
36             {
37                 ab[AB++] = b[i]+a[j];
38             }
39         }
40         sort(ab,ab+AB);
41         for(int i=0;i<C;i++)
42         {
43             scanf("%d", &c[i]);
44         }
45         printf("Case %d:
", Case++);
46         scanf("%d", &S);
47         for(int i=0;i<S;i++)
48         {
49            scanf("%d", &X);
50            int ans =0;
51            for(int j=0;j<C && !ans;j++)
52            {
53                ans=find_AB(X-c[j]);
54            }
55            printf("%s
", ans == 0?"NO":"YES");
56         }
57     }
58     return 0;
59 }

Problem E HDU 2199  Can you solve this equation? 简单的二分

 1 #include <stdio.h>
 2 #include <math.h>
 3 #define eps 1e-10
 4 
 5 double f(double x)
 6 {
 7     return 8*pow(x,(double)4) + 7*pow(x,(double)3) + 2*pow(x,(double)2) + 3*x + 6;
 8 }
 9 
10 int main()
11 {
12     int T;
13     while(~scanf("%d", &T))while(T--)
14     {
15         double l = 0, r = 100, x, y;
16         scanf("%lf", &y);
17         if(y<6 || f(100)<y){printf("No solution!
");continue;}
18         while(l+eps<r)
19         {
20             x = (r+l)/2;
21             double a = f(x);
22             if(a+eps < y)l=x;
23             else if(a-eps > y)r = x;
24             else break;
25         }
26         printf("%.4lf
", x);
27     }
28     return 0;
29 }

Problem F HDU 2899 Strange fuction

求函数的最小值，就只需要将方程求导，倒数为0的点就是所求，接下来就是同上了

 1 #include <stdio.h>
 2 #include <math.h>
 3 #define eps 1e-10
 4 
 5 double x,y;
 6 
 7 double f(double x)
 8 {
 9     return 42*pow(x,(double)6) + 48*pow(x,(double)5) + 21*pow(x,(double)2) + 10*x ;
10 }
11 
12 double g(double x)
13 {
14     return 6 * pow(x,7)+ 8*pow(x,6) + 7*pow(x,3) + 5*pow(x,2) - y*x;
15 }
16 
17 int main()
18 {
19     int T;
20     while(~scanf("%d", &T))while(T--)
21     {
22         double l = 0, r = 100;
23         scanf("%lf", &y);
24         if(y<6 || f(100)<y){printf("No solution!
");continue;}
25         while(l+eps<r)
26         {
27             x = (r+l)/2;
28             double a = f(x);
29             if(a+eps < y)l=x;
30             else if(a-eps > y)r = x;
31             else break;
32         }
33         printf("%.4lf
", g(x));
34     }
35     return 0;
36 }

Problem G HDU 2298  Toxophily

这道题要求从0 0 打到x y已知初速度的最小出射角度，我的方法是按照公式

y = Vsin(Sita)*t - G*t^2/2和

x = Vcos(Sita)*t;

对于已知可以达到x求出可以达到最高的y的角度，再在0到这个范围二分

之所以要求出到达x时所能到达的最高高度，是由于将t消去（下面的式子代入上式）后，y不是单调函数而是先增后减，而题目又是要求最小的出射角，那我们必然可以求出最大高度时的角度，那么角度在0到这个范围中一定有一个是原来的解，二分即可

 1 #include <stdio.h>
 2 #include <math.h>
 3 const double eps = 1e-10;
 4 const double eps1 = 1e-7;
 5 const double pi = 4 * atan(1.0);
 6 const double G = 9.8;
 7 double V, x, y;
 8 
 9 
10 double f(double sita)
11 {
12     return V*sin(sita)*x/(V*cos(sita)) - (G*x*x)  /  ( 2 * V * V * (cos(sita) * cos(sita))  ) ;
13 }
14 
15 int main()
16 {
17     int T;
18     while(~scanf("%d", &T))while(T--)
19     {
20         scanf("%lf %lf %lf", &x, &y, &V);
21 
22         if(x==0 && (V*V/(2*G)-y) > eps ){printf("%lf
",pi/2); continue;}
23         else if(x==0 && (y - V*V/(2*G))>eps ){printf("-1
"); continue;}
24 
25         double  l = 0, r = pi/2+0.5;
26         double mid = 0, midmid = pi/2;
27         while(midmid - mid > eps)
28         {
29             mid = (l+r)/2;
30             midmid = (mid+r)/2;
31             double mid_val = f(mid);
32             double midmid_val = f(midmid);
33             if(midmid_val < mid_val)   r = midmid;
34             else l = mid;
35         }
36         if(y > f(mid)){printf("-1
"); continue;}
37         double ans = 0;
38         l = 0, r = mid;
39         while(1)
40         {
41             mid = (l+r)/2;
42             double temp = f(mid);
43             if(fabs(y - temp) < eps1){ans = mid;break;}
44             else if(temp < y)  l = mid;
45             else r = mid;
46         }
47         printf("%lf
", ans);
48     }
49     return 0;
50 }

Problem H HDU 4355  Party All the Time

暂未搞出

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/gj-Acit/p/3234096.html