第二次组队赛之：Expanding Rods&&Aggressive cows&&Can you solve this equation?&&Strange fuction

Expanding Rodshttp://poj.org/problem?id=1905

思路；先是一定要想到数学模型！！！

从题目类型就是用二分法的：（以前应该做过的）就是一段圆的弧长

注意是对半径进行二分！！（弧长公式：半径乘对应的角度）（一定要找到进行二分的对象）

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 double l;
 7 double f(double a)
 8 {
 9     return 2*asin(l/(a*2))*a;//反三角sin（）
10 }
11 double g(double b)
12 {
13     return b-sqrt(b*b-l*l/4);
14 }
15 int main()
16 {
17     double n,c,r1,r2,L,mid;
18     while(scanf("%lf%lf%lf",&l,&n,&c)!=EOF)
19     {
20         if(l<0&&n<0&&c<0)
21             break;
22         if(l==0||n==0||c==0)
23         {printf("0.000
");continue;}
24         r1=l/2;//左半径最小应大于这个数。
25         r2=l;//注意一个数学的简单现象：半径越长，弧长越短。
26         L=(1+n*c)*l;
27         while(f(r2)>L)
28             r2=r2*2;//这里判断求一个比实际弧长小的数就行了。
29         while(fabs(f(r1)-f(r2))>1e-9)//对半径进行二分
30         {
31             mid=r1/2+r2/2;
32             if(f(mid)>L)
33                 r1=mid;
34             else if(f(mid)<L)
35                 r2=mid;
36             else
37                 break;
38         }
39         printf("%.3lf
",g(mid));
40     }
41     return 0;
42 }

Aggressive cowshttp://poj.org/problem?id=2456

二分+贪心：思路：就是把那个距离进行二分（当全部大于这个距离时，把它放大，不然就缩小）

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,a[100005],c;
 6 int judge(int s)
 7 {
 8     int i,number=1,frontt=0;
 9     for(i=0;i<n;i++)
10     {
11         if(a[i]-a[frontt]>=s)
12         {
13             number++;frontt=i;
14             if(number==c)
15             return 1;
16             }
17     }
18     return 0;
19 }
20 int main()
21 {
22         int i,left,right,mid;
23         scanf("%d%d",&n,&c);
24         for(i=0;i<n;i++)
25             scanf("%d",&a[i]);
26         sort(a,a+n);
27         left=0;
28         right=a[n-1]-a[0];
29         while(left<=right)
30         {
31             mid=(left+right)/2;
32             if(judge(mid))//判断在这个距离时，能不能全部放入
33                 left=mid+1;
34             else
35                 right=mid-1;
36         }
37         printf("%d
",right);
38     return 0;
39 }

Can you solve this equation?http://acm.hdu.edu.cn/showproblem.php?pid=2199

一个最基础的二分题：就是从一个函数入手（一般题目最后都要找到这类的函数）

 1 #include<stdio.h>
 2 #include<math.h>
 3 int main()
 4 {
 5     int y,T;
 6     scanf("%d",&T);
 7     while(T--)
 8     {
 9         double  l=0,r=100,mid,sum;
10         scanf("%d",&y);
11         if(y<6||y>807020306)
12         {
13             printf("No solution!
");
14             continue;
15         }
16         while(r-l>1e-9)//一般都要大于这个数才准确吧。（小数点后九位）
17         {
18             mid=(r+l)/2;
19             sum=pow(mid,4)*8+7*pow(mid,3)+mid*mid*2+3*mid+6;
20             if(sum>y)
21                 r=mid;
22             else if(sum<y)
23                 l=mid;
24             else if(sum==y)
25                 break;
26         }
27         printf("%.4lf
",mid);
28     }
29     return 0;
30 }

Strange fuctionhttp://acm.hdu.edu.cn/showproblem.php?pid=2899

一个基础的三分题目：（不必多说，一般此类题目的裸体就是这个样子。）

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 double y;
 7 double dis(double x)
 8 {
 9     return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*x*x-y*x;
10 }
11 int main()
12 {
13     double left,right,mid,mmid,t2,t1;
14     int t;
15     scanf("%d",&t);
16     while(t--)
17     {
18         scanf("%lf",&y);
19         left=0;right=100;
20         while(right-left>1e-9)
21         {
22             mid=left/2+right/2;
23             mmid=mid/2+right/2;
24             t2=dis(mid);t1=dis(mmid);
25             if(t2>t1)
26             {
27                 left=mid;
28             }
29             else if(t2<t1)
30             {
31                 right=mmid;
32             }
33             else
34                 break;
35         }
36         printf("%.4lf
",t1);
37     }
38     return 0;
39 }