​

1. 题目描述

2. 思路分析

整体思路：二分答案

设置一个变量longest来记录最长木头的长度，sum记录切成的小段数量之和。

令左边界l=0，右边界l=longest。

写一个bool类型的check()函数，将mid（即(l+r)/2）传递给形参x，算不同mid下能得到的段数之和sum。（通过遍历每个木头，算每个木头在不同mid下切割后的得到的段数，也就是下图代码中的a[i]/x），当sum>=k，返回true，否则返回false。当check()函数返回true时，让左边界l=mid，否则让右边界r=mid，这样不断二分，直到l+1==r时退出循环。

最后输出l即可。

3. 代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int a[N], n, k, longest, ans;
ll sum;

bool check(int x)
{
   
    sum = 0;
    for (int i = 1; i <= n; i++)
        sum += a[i] / x;
    if (sum >= k) return true;
    else return false;
}

int main()
{
   
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
   
        cin >> a[i];
        longest = max(a[i], longest);
    }
    int l = 0, r = longest;
    while (l + 1 < r)
    {
   
        int mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << l << endl;
    return 0;
}

​