题意:原来有n根木棒,然后至少分成k根长,求每根木棒的长度最长为多少。
思路:一个很显然的二分法求解,因为按照题目的意思肯定有一个是最长的,但是还要注意是否为单调变化,单调则用二分,有极值则为三分法,通过打表我们知道是单调的。
特判:结果为0的时候,也就是怎么也找不到一个长度满足题意。
代码:
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
int n,k;
bool judge(int x){ //判段函数
int ans=0;
for(int i=0;i<n;i++){
ans+=(a[i]/x);
}
if(ans>=k) return true;
return false;
}
int main(){
cin>>n>>k;
int mx=-1;
for(int i=0;i<n;i++){
cin>>a[i];
mx=max(mx,a[i]);
}
int l=1,r=mx,mid; //规定左右界限
int ans=0; //注意这里要先让ans=0,因为可能有找不到的情况
while(l<=r){
mid=(l+r)>>1;
if(judge(mid)){
ans=mid; //注意这里记录结果
l=mid+1;
}
else r=mid-1;
}
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号