原题链接:https://www.luogu.com.cn/problem/P2440
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;
}