开始预习二分法啦~

 （二分，最大值最小化）

题意：将N个账款分割成M个财务期，使得每个分期账款和的最大值最小。

题解：贪心思想，二分法。上界为N天花费总和，下界为每天花费的最大值。根据mid值遍历n天花费看是否满足M各财务期条件

1 #include
      
        2 #include
       
         3 using namespace std; 4 int main(){ 5     int n,m,i,cnt,a[100001],ma=0,s=0; 6     scanf("%d%d",&n,&m); 7     for(i=0;i
        
         >1;15         cnt=1;16         for(s=i=0;i
         
          mid){cnt++;s=a[i];}19         }20         if(cnt<=m) r=mid;21         else l=mid+1;22     }23     printf("%d\n",l);24     return 0;25 }
         
        
       
      

 

（二分，最小值最大化）

题意：一条长为L的河，除了起始点还有N个石子，分别距离起点Di，求去掉M个石子后相邻石子最小距离的最大值。

题解：上界为河长L，下界为初始时两相邻石子间最小距离，根据mid值遍历N个石子看是否满足移除M石子的条件。

1 #include
      
        2 #include
       
         3 using namespace std; 4 int main(){ 5     int L,n,m,i,l,r,mid,cnt,s,a[50002]; 6     scanf("%d%d%d",&L,&n,&m); 7     for(i=1;i<=n;++i) scanf("%d",&a[i]); 8     a[0]=0; 9     sort(a,a+n+1);10     l=r=L;11     for(i=1;i<=n;++i) l=min(l,a[i]-a[i-1]);12     while(l
       
      

 

（二分，几何）

题意：一根棍子，受热后长度会变为L' = (1+n*C)*L（棍子变为圆弧）。问受热后棍子的中点距离地面的高度h为多少。

题解：做这题我复习了一下相交弦定理（初中学的都快忘了）：若AB是直径，CD垂直AB于点P，则 =PA·PB。

直接二分高度，算出半径和弧度，然后将算出的弧长与实际弧长比较。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define eps 1e-4 5 using namespace std; 6 int main(){ 7     double L,n,c,L1,sita,l,r,mid,R; 8     while(scanf("%lf%lf%lf",&L,&n,&c)==3){ 9         if(L<0||n<0||c<0)break;10         L1=(1+n*c)*L;11         l=0; r=L/2;12         while(l+eps
        
       
      

 

（二分）

题意：有n块高度为1，半径不等的圆柱形披萨，要将其“平均”（每份体积相等，形状无要求，但必须每份是从同一个披萨上得到的）分给（f+1）人。

题解：下界为0，上界为最大的披萨的尺寸，二分尺寸看能分给多少人。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define pi 3.14159265359//背一下咯 5 #define eps 1e-6 6 using namespace std; 7 int main(){ 8     int t,i,n,f,a[10001],R,cnt; 9     double l,r,mid;10     scanf("%d",&t);11     while(t--){12         scanf("%d%d",&n,&f);13         f++;//总人数记得加上自己14         l=r=0;15         for(i=0;i
         
          =f) l=mid;26             else r=mid;27         }28         printf("%.4f\n",(double)mid*pi);29     }30     return 0;31 }
         
        
       
      

 

（高精度，二分）

题意：定义fibonacci数列前两项f[1] = 1，f[2] = 2。现在给你一个区间[a，b]，a <= b <= 10^100。问：区间[a，b]之间有多少个fibonacci数。

题解：先算出480个斐波那契数（第480个斐波那契数是101位了）。二维数组F[i][]表示第i个斐波那契数，二分查找a,b位置，如果找到的位置不是斐波那契数，则返回第一个比它大的斐波那契数的位置，注意对b判断作标记。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int N=482; 7 const int M=102; 8 int F[N][M],f; 9 char Fi[N][M],a[M],b[M];10 void Fib(){11     int i,j,k;12     F[1][0]=1;F[2][0]=2;13     for(i=3;i
          
           =10){17                 F[i][j+1]+=F[i][j]/10;18                 F[i][j]%=10;19             }20         }21     }22     for(i=1;i
           
            =0;--j){ //清除前导024 if(F[i][j]==0)continue;25 else break;26 }27 k=0;28 while(j>=0){29 Fi[i][k++]=F[i][j]+'0';30 j--;31 }32 Fi[i][k]='\0';33 }34 }35 int cmp(char*a,char*b){36 int La=strlen(a);37 int Lb=strlen(b);38 if(La!=Lb) return La
           
          
         
        
       
      

 

【如有错误，敬请指正，欢迎交流】