P2440 木材加工

P2440 木材加工

P2440 木材加工

题意

木材厂有 n 根原木,现在想把这些木头切割成 k 段长度均为 l 的小段木头(木头有可能有剩余),希望得到的小段木头越长越好,请求出 l 的最大值,如果连 1cm 长的小段都切不出来,输出 0。

思路

  1. 首先要定义一个函数,去查找答案。
  2. 在主函数中应用函数,最后输出答案。

坑点

  1. 要想到用二分。

算法一:二分答案

时间复杂度

On

实现步骤
  1. 首先要定义一个函数,去查找答案。
  2. 在主函数中应用函数,最后输出答案。
  3. 在主函数中进行sort排序,为避免小错误。
代码
 #include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,k;
int a[1000005];
int find(int l,int r)
{
	while(l<=r)
	{
		int mid=(l+r)/2;
		int ans=0;//n/l
		for(int i=0;i<n;i++)
		{
			ans+=a[i]/mid;
		}
		if(ans>=k)
		{
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	return r;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a,a+n);
	int l=1,r=a[n-1];
	int x=find(l,r);
	cout<<x;
	return 0;
}

总结

要掌握二分答案。