很显然的一道二分题板子题
要我们去找这个值显然很复杂,但是给我们一个答案要我们去判断一下这个是否满足要求就比较简单,这就是二分答案的思想,化复杂的问题为判定问题。现在给我们一个长度,我们要验证它是否满足条件只需要所有长度/这个长度之和就是能做的棍子数>=目标棍子数,这样就行了,然后不断二分更新答案即可。
代码
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 2e5 + 10; ll a[maxn],n,k; bool check(ll mid){ ll s = 0; for(ll i = 1;i <= n; i++){ s += a[i] / mid; } return s >= k; } void solved(){ cin>>n>>k; for(ll i = 1; i <= n; i++)cin>>a[i]; ll l = 1,r = 1e9 + 10; ll ans = 0; while(l <= r){ ll mid = (l + r)>>1; if(check(mid)){ l = mid + 1;ans = mid; } else r = mid - 1; } cout<<ans<<endl; } int main(){ solved(); return 0; }