这题算是水题。。
题目大意:
给N根长度不一样的木棍,现在可以对木棍进行剪裁,问经过剪裁以后能否得到K根长度一样的木棍。多出来的可以不用。问最长可以剪裁成多少长度相同的K根木棍。
N<=200000
思路:
二分长度。
然后每次判断当前二分的长度能不能组成K根木棍。
代码:
#include<bits/stdc++.h> using namespace std; int n,k,a[200040]; long long sum; bool check(long long x){ int t=0; for(int i=1;i<=n;i++){ t+=a[i]/x; if(t>=k)return true; } return false; } int main() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i]; long long l=0,r=sum/k; while(l<r){ long long mid=l+r+1>>1; if(!check(mid))r=mid-1; else l=mid; } cout<<r<<endl; return 0; }