【题目描述】

小A是某工地的计算工程师。工地现有 n 根钢管，第 i 根钢管的长度为 ai。

现在想用这 n 根钢管来做一个支撑用的柱子。我么可以切割这些钢管成为更短的钢管，但是不能缝合两根钢管。为了安全起见，柱子必须用 至少 k 根长度相同的钢管加上混凝土制成，并且要求钢管长度必须为 整数。

小A想知道，这个柱子最高能建成多高（钢管可以有剩余）。

【输入描述】

输入第一行一个整数  。

接下来一行输入 n 个空格隔开的整数 ，表示每根钢管的长度。

【输出描述】

输出最大的高度。

【样例输入1】

2 4  8 4

【样例输出1】

2

【样例输入2】

8 8  12 3 14 12 14 20 4 8

【样例输出2】

7

【题目分析】

• 题目的意思是切割最短的钢管的长度是多少，而不是切割完毕后，这些钢管加起来长多少。

• 非常经典的二分法 （最大化平均值问题）。

我们可以假设按照最短的那个进行切割，比如上图，最短的钢管是4。那么一共可以切成(4/4)+(8/4)=3块。不满足题目要求。所以不行，要把切割的长度缩小。

关于缩小，你实际上可以用暴力穷举，按照4切割，切割出来的数量少了，就按照3切割，如果还是少了，就按照2切割。

那么实际上，我们一直在“找”合适的切割长度来切割这些钢管。如果按照暴力枚举一个个挨个试，时间肯定是比较长的。那么我们不妨用二分的方法试，

这样试起来比较快。

【思路及方法】

我们设立一个最小值和最大值，然后取中间值，用这个中间值来切割钢管，如果比K大，说明当前切割的方法可行，但是，不一定是最优的，因为题目要保证

切割下来的钢管尽量的高。所以继续切割，直到左端点和右端点出现重合的现象。

用这个方法解释上面的例子：

我们假设钢管长度最小是1，最大是100。（题目一般会给出）

第一次我们取中间值 (100+1)/2=50。我们按照50的长度对两根钢管进行切割（结论是0，不符合条件）,更新右端点值为50；

我们再取51 (1+50)的中间值25，我们按照25的长度对两根钢管进行切割（结论是0，不符合条件），更新右端点值为25；

我们再取26 (1+25)的中间值13，我们按照13的长度对两根钢管进行切割（结论是0，不符合条件），更新右端点值为13；

我们再取14 (1+13)的中间值7，我们按照7的长度对两根钢管进行切割（结论是1，不符合条件），更新右端点值为7；

我们再取4(1+7)的中间值4，我们按照4的长度对两根钢管进行切割（结论是3，不符合条件），更新右端点值为4；

我们再取2 (1+4)的中间值2，我们按照2的长度对两根钢管进行切割（结论是6，符合条件）。

【参考答案】

#include <iostream>  using namespace std;  //想要分割出来的钢管高度越高，那么能分割出来的就越少  int a[10005]; //把每根钢管的长度存放起来  int main(){      int n,k;      cin >> n >> k;      //最后输出的最大高度，这些钢管的根数一定是大等于k的      for(int i=0;i<n;i++){          cin >> a[i];      }      int l = 0 , r = 100000001; //设起始最大高度为r 右边界      while(l < r){          int mid = (l + r) >> 1;// 二分查找  		int cnt = 0; //记录当前钢管高度的总根数          for(int i=0;i<n;i++){              cnt += a[i] / mid;              //每个钢管除以当前高度，就可以得到这个钢管可以分割出来的根数          }          if(cnt >= k){               //如果说当前这个高度分割出来的根数大等于k              //那么这个mid是可行的，我们就可以扩大左边界值              l = mid + 1;          }else{              r = mid;              //否则的话，这个mid就是太高了，就可以把右边界缩小          }      }      cout << r - 1 << endl;         //这里输出l-1或者r-1都可以，因为最后结果出来l与r是相等的      return 0;  }

【思考】

为什么二分要上面那样写？还有其他写法吗？建议多做几道题再回来看。

    while(l < r){          int mid = (l + r) >> 1;  		int cnt = 0;           for(int i=0;i<n;i++){              cnt += a[i] / mid;          if(cnt >= k){               l = mid + 1;          }else{              r = mid;          }      }      cout << l-1 << endl; // 或r-1

多做几道题总结一下就会发现，这类题目的思想一样，只不过写法不一样。

基本原理是：我们让左个区间始终满足，右区间始终不满足（也可以反过来）。每次中间值步进一个值，不断试探。直到不满足题目条件为止。

比如上面这个题目，我们可以有这样两个考虑：

（1）如果有一个mid满足条件，将mid+1后不满足条件，那么mid就是最优解。（上面代码中L=mid+1。所以最终要输出L-1）

（2）如果有一个mid不满足，将mid-1后满足，那么mid-1就是最优解。（上面的代码R=mid，所以最终要输出R-1）

其实，上面的代码还有其他写法。最简单的其实就是移项操作。比如

while(L<R) 完全可以写成 while(L-R<0) 或者其他符合原题意的式子。

如果不考虑移项，我们可以考虑其他写法。比如：

 while(L+1 < R){          int mid = (L + R) >> 1;  		int cnt = 0;           for(int i=0;i<n;i++){              cnt += a[i] / mid;          if(cnt >= k){               L = mid;          }else{              R = mid;          }      }      cout <<L<< endl; // 或R-1

这个也是完全成立的。我们换个思路，反推，根据代码思考过程。上面这段代码while循环不成立时，L+1>=R。我们可以这么认为：“是因为L+1导致不符合题意，所以答案要输出L或者R-1”。

当这类题目做的多了，自然就会发现规律，循环条件，左右区间端点值的取法是配套的。基本原理就是上面说到，让左区间满足，右区间不满足，然后每次左区间加1，不断试探，直到不满足条件（当然，完全可以反过来考虑）。

(adsbygoogle = window.adsbygoogle || []).push({});