比较好的网页设计网站,免费模板简历网站,衡水精品网站建设价格,哈尔滨市公共资源交易中心原题链接#xff1a;https://www.luogu.com.cn/problem/P2440
1. 题目描述 2. 思路分析
整体思路#xff1a;二分答案
设置一个变量longest来记录最长木头的长度#xff0c;sum记录切成的小段数量之和。
令左边界l0#xff0c;右边界llongest。
写一个bool类型的check…原题链接https://www.luogu.com.cn/problem/P2440
1. 题目描述 2. 思路分析
整体思路二分答案
设置一个变量longest来记录最长木头的长度sum记录切成的小段数量之和。
令左边界l0右边界llongest。
写一个bool类型的check()函数将mid即(lr)/2传递给形参x算不同mid下能得到的段数之和sum。通过遍历每个木头算每个木头在不同mid下切割后的得到的段数也就是下图代码中的a[i]/x当sumk返回true否则返回false。当check()函数返回true时让左边界lmid否则让右边界rmid这样不断二分直到l1r时退出循环。
最后输出l即可。
3. 代码实现
#includebits/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;
}
