题意: 华华希望裁剪出至少根木棍,并且木棍的长度越长越好。
题解: 简单思考一下,发现二分最大长度即可,每次二分的时候表示判定以
为当前木棍的最大长度是否可剪出至少
根木棍,如果可以说明最大长度至少为
,若不行则说明长度最长为
。
的时间复杂度为
,总时间复杂度为
。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 2e5 + 10; int q[N], n, k; ll check(int x) { ll res = 0; for(int i = 0; i < n; i++) res += q[i] / x; return res; } int b_s(int l, int r, ll k) { //l,r是木棍的长度 while(l < r) { int mid = l + r + 1 >> 1; if(check(mid) >= k) l = mid; else r = mid - 1; } return l; } int main() { scanf("%d%d", &n, &k); int Ma = 0; for(int i = 0; i < n; i++) scanf("%d", &q[i]), Ma = max(Ma, q[i]); int t = b_s(0, Ma, (ll)k); printf("%d\n", t); return 0; }
另:由于题目中说的初始木棍长度是非负整数,而数据范围给的,也许这就是二分的左边界不能为1的原因?(希望会的大佬可以教教我QwQ