2644: 烤干机

解题思路:一开始想的是用贪心去解，做完发现只得了36分，动态规划想不来，做完某个二分答案得题目后发现能用二分答案去解这道题

用二分法去枚举要烘干衣服最少用多少时间.

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
int y[500005];
int check(int t)
{
	int x[500005];
	for(int i=0;i<n;i++)
	{
		x[i]=y[i];
	}
	for(int i=n-1;i>=0;i--)//自然风干的量
	{
		x[i]-=t*a;
		if(x[i]<0)
		{
			x[i]=0;
		}
	}
	for(int i=n-1;i>=0;i--)//最好得肯定每一个单位时间都要用上烘干机
	{
		t-=x[i]/b;
		if((x[i]/b)*b!=x[i])
		{
			t--;
	         }
	}
	if(t>=0)//烘干机没有用完，说明时间或许可以再减少
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
int main()
{
	
	scanf("%d%d%d",&n,&a,&b);

	for(int i=0;i<n;i++)
	{
		scanf("%d",&y[i]);
	}
	sort(y,y+n);
	int l=1,r=y[n-1];
	int ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		//printf("%d",mid);
		if(check(mid)==1)
		{
			ans=mid;
			r=mid-1;
		}
		else if(check(mid)==0)
		{
			l=mid+1;
		}
	}
	printf("%d",ans);
	return 0;
}