3089171_ac_121ms_164k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 54 行

#include <stdio.h>
#include <math.h>

int main()
{
	int n, k, i;
	__int64 min, max, mid;
	__int64 len[10001];
	double t;
	int cnt;

	scanf("%d%d",&n,&k);
	for(i = 0; i < n; i++)
	{
		scanf("%lf",&t);
		len[i] = (__int64)(t*100.0);
	}
	min = 0; max = 10000000;
	while(min < max)
	{
		mid = (max+min)/2;
		if(mid==0)
		{
			min = 1;
			break;
		}
		cnt = 0;
		for(i = 0; i < n; i++)
		{
			cnt += len[i]/mid;
		}
		if(cnt < k)
			max = mid;
		else
			min = mid+(min==mid);
	}
	while(min>0)
	{
		cnt = 0;
		for(i = 0; i < n; i++)
		{
			cnt += len[i]/min;
		}
		if(cnt < k)
			min--;
		else
			break;
	}
	t = min;
	t /= 100.0;
	printf("%.2lf\n",t);
	return 0;
}