题目：

题意：

一条河长度为 L，河的起点(Start)和终点(End)分别有2块石头，S到E的距离就是L。

河中有n块石头，每块石头到S都有唯一的距离

问现在要移除m块石头（S和E除外），每次移除的是与当前最短距离相关联的石头，

要求移除m块石头后，使得那时的最短距离尽可能大，输出那个最短距离。

和3273差不多。。。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int maxn = 50000+10; 8 int a[maxn]; 9 10 int main()11 {12     int l, n, m, i;13     int low, mid, high, sum, cnt;14     cin>>l>>n>>m;15     a[n+1] = l;16     low = l;17     high = l;18     for(i = 1; i <= n; i++)19     {20         cin>>a[i];21     }22     sort(a+1, a+n+1);23     for(i = 1; i <= n+1; i++)24     if(a[i]-a[i-1]
          
           =low) //注意‘=’号28 {29 sum = 0; cnt = 0;30 mid = (high+low)/2;31 for(i = 1; i <= n+1; i++)32 {33 sum += a[i]-a[i-1];34 if(sum
          
         
        
       
      
     

 

 

以后还是用这种形式的二分吧

while(left<right)

{

if()

left=mid+1;

else right=mid;

}

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int maxn = 50000+1000; 8 int a[maxn]; 9 10 int main()11 {12     int l, n, m, i, f;13     int low, mid, high, sum, cnt;14     cin>>l>>n>>m;15     a[n+1] = l;16     low = l;17     high = l;18     for(i = 1; i <= n; i++)19     {20         cin>>a[i];21     }22     sort(a+1, a+n+1);23     for(i = 1; i <= n; i++)24     if(a[i]-a[i-1]
          
           low)29 {30 sum = 0; cnt = 0;31 mid = (high+low)/2;32 for(i = 1; i <= n; i++)33 {34 sum += a[i]-a[i-1];35 if(sum
           
             m)41 {42 high = mid;43 f = 1;44 }45 else46 low = mid+1;47 //cout<
            
             <
             
              <
              
               <
              
             
            
           
          
         
        
       
      
     

 

还有

这篇博客以这两道题为例， 说明了二分时的易错的情况