P2440 木材加工
- 分析：根据题意，先对所有的木材长度进行排序方便二分查找，写一个查找函数，每个木材都除以当前的切割长度（mid），看能切出几段，如果切出的段数大于要求的段数，证明查找失败，在主程序内的mid（也就是当前的切割长度）就要将范围缩小一半，如果得出的段数少于给定段数，范围就反向缩小一半。主程序内有一个经典的二分查找模板，直接根据题意套用即可。
-
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,a[1000001];
bool check(int mid)
{
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=a[i]/mid;//看每次能切出几个小段 再把小段加起来
}
return ans>=k;//不符合题意 裁的段数多了
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int l=1,r=a[n],ans=0;
while(l<=r)//二分查找模板
{
int mid=(l+r)/2;
if(check(mid))
{
l=mid+1;//数小了 看从mid往后的
ans=mid;
}
else r=mid-1;//数大了 看从mid往前的
}
cout<<ans;
return 0;
}