HDU 4190 2分

HDU 4190 二分

不多说了，二分题目，都是别人提示了，我喜欢自己想出来，不过刚刚看到这题，就想到这个方法了，思路没定行，出题人就喊着二分了，╮(╯▽╰)╭

 

 

#include <iostream>
using namespace std;

int city[500001];

int n,m;

inline bool Jude(int mid)
{
	int sum=0;
	for (int i=0;i<n;i++)
	{
		sum+=city[i]/mid;
		if(city[i]%mid) sum++;
		if(sum>m) return false;
	}
	return true;
}

int main()
{
	int mid,i,st,en;
	while(scanf("%d%d",&n,&m)!=EOF&&(n!=-1||m!=-1))
	{
		st=0;//装的最少的
		en=-1;//装的最多的
		for(i=0;i<n;i++)
		{
			scanf("%d",&city[i]);
			if(city[i]>en) en=city[i];
		}
		while (st<en)
		{
			mid=(st+en)>>1;
			if(Jude(mid))//投票箱够
			{
				en=mid;
			}
			else//投票箱不够
			{
				st=mid+1;
			}
		}
		printf("%d\n",en);
	}
	return 0;
}