题目

题目描述：
二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？

输入描述：
第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数Li表示每根木棍的初始长度。

输出描述： 
输出一行一个非负整数表示每根木棍的最大长度。

解析

首先题目这么长，我们来看一遍题目
  • 看过一遍以后这道题的意思其实就是：N根木棍裁剪后长短相同，最长是多少。
那么问题就来了：
  1. 木棍不可能裁的比自己还长。
  2. 木棍在裁剪过程中很可能会有浪费，而且浪费木材不能使用。
所以现在我们可以构建基本思路：
  1. 将数据存入一个数组使用
  2. 用二分法（下面列专栏讲）查找长度的范围，知道找到答案（因为是非负整数，所以一定可以找到答案）
只有两条？对，思路就是这么简单，但我最开始不会orz，哭唧唧
憨憨还试着从一个较大值一个一个试下来。在大佬的思路提示下才理解

二分

关于这道题，我就有所不知。
我们常用的二分法：做查找类运算，利用缩减范围而达到查找到所需的位置。
惯性思维让我对于二分只想到用在查找数据上（其实我都快忘了二分了）
然而这道题还真是个查找题。。。
拿这道题举例：
  1. 我们已知需求的木棍范围在0~1e9
  2. 对该区间进行二分查找，在区间0~1e9中找到最长的那个K
  3. 每次对中点mid（K的假定值）进行操作，判断最长K是在左区域还是右区域，以此减少一半的范围
  4. 以此类推，直到相等
这是二分的基本操作： 
while (left < right) {
    int mid = left + right>> 1;
        int key = 0；
        /****************************
        在这里进行对key的基本操作
        ****************************/
    if (mid >= key) left = mid;//此处mid不能+1的原因是：判断包括了mid==key的情况
    else right = mid - 1;
        //此处视key的情况判断左右区间
}

AC代码 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX = 1e9 + 9;

int main() {
    js;
    ll N, K; cin >> N >> K;
    vector<ll> L;
    for (ll i = 0; i < N; i++) {
        ll t; cin >> t;
        L.push_back(t);
    }
    ll left = 0, right = MAX;//左右范围
    while (left < right) {
        ll sum = 0, mid = left + right + 1 >> 1;
                //+1是为了让分母不为0，mid只是一个中间值，改变一点影响不大
        for (ll i = 0; i < N; i++)
            sum += L[i] / mid;
                //sum求出在mid值下最大可以得到的木条数
        if (sum >= K) left = mid;
        else right = mid - 1;
                //可以得到的多于你要的数量时，表示mid短了（短了才会更多）。反之亦然
    }
    cout << left << endl;
    return 0;
}