题目:
考察点:
二分--假设某个值存在。
侃侃:
这道题可以说是二分中的一道模板题,我们先假设某个值成立,然后带入到已知条件中,判断当前值 是否满足所有的条件,若满足条件,看是否是最优的,如果不是最优的(还有更优的),就进一步缩小 范围,直到找到一个最优的值。
Code:
#include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 2e5 + 10; int a[maxn]; int n,k; int Check(int x) { int ans = 0; // 假设当前满足条件的木棍长度是 x ,计算可以分成多少根木棍 for(int i = 1; i <= n; i ++) { ans += a[i] / x; } return ans; } int main(void) { scanf("%d%d",&n,&k); for(int i = 1; i <= n; i ++) { scanf("%d",&a[i]); } // 排序寻找一下最大值,缩减二分的范围 sort(a + 1,a + 1 + n); // 左端最少是 0 ,满足一定可分 int l = 0,r = a[n]; while(l < r) { // + 1 防止出现死循环 int mid = (l + r + 1) >> 1; if(Check(mid) < k) r = mid - 1; else l = mid ; } printf("%d\n",r); return 0; }
后记:
如有解释的不到位的地方,欢迎各位大佬在评论区留言。
欢迎各位大佬访问本菜鸡的博客:
https://www.cnblogs.com/prjruckyone/