题意:原来有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; }