二分

hdu 4190 Distributing Ballot Boxes

http://acm.hdu.edu.cn/showproblem.php?pid=4190

【题意】题目看来半天。。n个城市所有的人要投票，投票箱的大小可以无限大（投票箱全部相同，大小相等），我们现在要求的是最小的投票箱容纳量。

就二分吧只有一个要注意的就是一个函数 ceil（）的用法

函数名： ceil

用法： double ceil(double x);

功能：返回大于或者等于指定表达式的最小整数

头文件：math.

如a = [-1.9, -0.2, 3.4, 5.6, 7, 2.4+3.6i]

圆整后：a=[-1,0,4, 6, 7 ,3+4i]

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include<cmath>
 5 
 6 #define INF (1<<30)
 7 using namespace std;
 8 
 9 int a[500002],n,b;
10 
11 int ok(int x)
12 {
13     int ans=0;
14     for(int i=0;i<n;i++)
15         ans+=ceil(a[i] * 1.0/x);
16     return ans<=b;
17 }
18 
19 int find1(int l,int r)
20 {
21     while(l<r)
22     {
23         int m;
24         m=(l+r)/2;
25         if(ok(m))
26             r=m;
27         else l=m+1;
28     }
29     return r;
30 }
31 
32 int main()
33 {
34     int i,j;
35     while(scanf("%d%d",&n,&b))
36     {
37         if(n==-1&&b==-1)
38             break;
39         int maxx=0;
40         for(i=0;i<n;i++)
41             {
42                 scanf("%d",&a[i]);
43                 if(a[i]>maxx)
44                    maxx=a[i];
45             }
46         printf("%d
",find1(0,maxx));
47     }
48    return 0;
49 }

View Code

hdu 2141 Can you find it?

http://acm.hdu.edu.cn/showproblem.php?pid=2141

【题意】分别给定三组A、B、C的值和S值，问是否能找到Ai、Bj、Ck，使得Ai+Bj+Ck = S。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #define INF (1<<30)
 5 using namespace std;
 6 
 7 int a[505],b[505],c[505],num[250002];
 8 
 9 int find1(int l,int r,int x)
10 {
11     while(l<=r)
12     {
13         int m;
14         m=(l+r)/2;
15         if(num[m]==x)
16             return 1;
17         if(num[m]<x)
18             l=m+1;
19         else r=m-1;
20     }
21     return 0;
22 }
23 
24 int main()
25 {
26    int i,j,n,m,k,s,t,case1=1;
27    while(~scanf("%d%d%d",&n,&m,&t))
28    {
29        for(i=0;i<n;i++)
30           scanf("%d",&a[i]);
31        for(j=0;j<m;j++)
32           scanf("%d",&b[j]);
33        for(k=0;k<t;k++)
34           scanf("%d",&c[k]);
35 
36        int temp=0;
37        for(i=0;i<n;i++)
38            for(j=0;j<m;j++)
39              num[temp++]=a[i]+b[j];
40        sort(num,num+temp);
41 
42        scanf("%d",&k);
43        printf("Case %d:
",case1++);
44        while(k--)
45        {
46            int flag=0;
47            scanf("%d",&s);
48            for(i=0;i<t;i++)
49                if(find1(0,temp-1,s-c[i]))
50                {
51                    flag=1;
52                    break;
53                }
54            if(flag)
55                printf("YES
");
56            else
57                printf("NO
");
58        }
59    }
60    return 0;
61 }

View Code

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

【题意】 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Y,给出每个y求出x 因为这个多项式是单调递增的所以可以用二分求解

求解的过程中要尽可能的精确我把精度开始设成了1e-6 还没过设成1e-7 才过

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 #define INF (1<<30)
 7 using namespace std;
 8 
 9 double ok(double x)
10 {
11     return 8*x*x*x*x+7*x*x*x+2*x*x+3*x+6;
12 }
13 
14 double find1(double l,double r,double y)
15 {
16         double m,ans;
17         while(r-l>(1e-7))
18         {
19 
20             m=(l+r)/2;
21             ans=ok(m);
22             if(y<ans)
23                 r = m-(1e-7);
24             else
25                 l = m+(1e-7);
26 
27         }
28         return (l+r)/2;
29 }
30 
31 
32 int main()
33 {
34     int i,t,j,m,n;
35     double y;
36     scanf("%d",&t);
37     while(t--)
38     {
39         scanf("%lf",&y);
40         if(ok(0.0)>y || ok(100.0)<y)
41         {
42             printf("No solution!
");
43             continue;
44         }
45         printf("%.4lf
",find1(0.0,100.0,y));
46     }
47    return 0;
48 }

View Code

hdu 4004 The Frog's Games

http://acm.hdu.edu.cn/showproblem.php?pid=4004

【题意】求青蛙在给定的跳跃次数M 以内跳过河。我们预先知道河宽L，河上有N块石头，青蛙可以在石头上停留。求青蛙的每次跳跃至少跳多远才能顺利过河。

#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF (1<<30)
using namespace std;
int m,n,l,a[500005];

int ok(int x)
{
    int temp=0,i,num=0;
    for(i=0;i<=n;)
    {
        if(++num>m||a[i]-temp>x)
            return 0;
        while(a[i]-temp<=x&&i<=n)
            i++;
        temp=a[i-1];


    }
    return 1;
}


int main()
{
    int i,j;
    while(~scanf("%d%d%d",&l,&n,&m))
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        a[n]=l;
        int left=0,right=l;
        while(left<right)
        {
            int m=(left+right)/2;
            if(ok(m))
                right=m;
            else
                left=m+1;
        }
        printf("%d
",left);
    }
    return 0;
}

View Code

hdu 1969 pie

http://acm.hdu.edu.cn/showproblem.php?pid=1969

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cmath>
 4 #define INF (1<<30)
 5 #define pi 4*atan(1.0)
 6 using namespace std;
 7 
 8 double a[10003];
 9 int n,r;
10 
11 int ok(double x)
12 {
13     int i,num=0;
14     for(i=0;i<n;i++)
15         num+=a[i]/x;
16     return num>=r+1;
17 
18 }
19 
20 
21 int main()
22 {
23     int i,j,t;
24     double temp;
25     scanf("%d",&t);
26     while(t--)
27     {
28         scanf("%d%d",&n,&r);
29         for(i=0;i<n;i++)
30         {
31             scanf("%lf",&temp);
32             a[i]=pi*temp*temp;
33         }
34 
35         double l=0, r=INF;
36         while(r-l>(1e-7))
37         {
38             double m=(l+r)/2;
39             if(ok(m))
40                 l=m;
41             else r=m-(1e-7);
42         }
43         printf("%.4lf
",l);
44     }
45     return 0;
46 }

View Code

poj 1905 Expanding Rods

http://poj.org/problem?id=1905

【题意】一根细杆长为l，能够压弯成为一段长为seg = (1+n*C)*l 的圆弧（如图所示），其中n为改变的温度，c为热膨胀系数。现在给出l, n, c的值，让你求出杆变形后，中间升高的距离h。

【思路】因为半径越长对应这段的弧长越短可以认为这个变化时单调的所以也可以用二分。枚举半径的长度然后可以根据半径和l 算出弧长temp 然后和seg比较再逐步缩小半径的范围就好了

我做的时候一直wa 想各种漏洞搞得条件越加越多越改越乱 = =

后来才晓得这里还要再加一个判断条件

if(n*c<0.000001)
{
printf("0.000 "); //不构成弧
continue;
}

桑心啊。。。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 const double INF=0xfffffff;
 8 int main()
 9 {
10     double n,c,l,m;
11     while(~scanf("%lf%lf%lf",&l,&n,&c))
12     {
13         if(l<0&&n<0&&c<0)
14             break;
15         if(n*c<0.000001)
16         {
17             printf("0.000
");
18             continue;
19         }
20         double l1=l*(1+n*c);
21         double left=0,right=INF;   //对 半径二分
22         while(right-left>1e-6)
23         {
24              m=(left+right)/2;    //printf("m  %lf
",m);printf("asin  %lf
",l/(2*m));
25              double angle;
26              angle=asin(0.5*l/m);
27              double temp=2*m*angle;          //printf("temp %lf
",temp);
28              if(temp>l1)
29                 left=m;
30              else right=m;
31         }
32         m=(left+right)/2;
33         double ans;
34         ans=m-(sqrt(m*m-l*l/4));
35         printf("%.3lf
",ans);
36     }
37     return 0;
38 }

View Code