木材加工

木材加工

思路：二分查找。

从木棍长度的中间分别向两边找，直至找出既满足木棍个数 长度又长的木棍长度。

代码如下：

#include<iostream>

using namespace std;

int n,k;

int len[1000010];

bool check(int mid)//mid为木棍长度

{

      long long sum=0;//sum记录木棍个数

      for(int i=0;i<n;i++)

      {//从第i根原木切出来多少个小段

           sum+=len[i]/mid;

      }

      return sum>=k;//k为想要的木棍个数

}

int main()

{

    cin>>n>>k;

      int max_len=0;//所有原木里最长的那根的长度

      for(int i=0;i<n;i++)

      {

           cin>>len[i];

           if(len[i]>max_len)

             max_len=len[i];

           }   

      int ans=0;

      int left=1;

      int right=max_len;

      while(left<=right)

      {

           int mid=(left+right)/2;

           if(check(mid))

           {

                 ans=mid;

                 left=mid+1;

           }

           else

           right=mid-1;

      }

      cout<<ans<<endl;

      return 0;

}