pku 1064 二分查找.txt

来自「ACM资料大集合」· 文本 代码 · 共 49 行

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
 
//PKU 1064 二分查找
#define NMAX 10005 
#define MINI 0.000001
double len[NMAX];

void solve(int num,double k)
{
	int i,ans;
	double sum=0,max=0;
	double low,high,mid;
	for(i=1;i<=num;i++)
	{
		if(len[i]>max) max=len[i];
		sum+=len[i];
	}
	low=max/k;
	high=sum/k;
	mid=(low+high)/2;
	while(high-low>MINI)
	{
		ans=0;
		for(i=1;i<=num;i++)
			ans+=(int)(len[i]/mid);
		if(ans>=k) low=mid;
		else high=mid;
		mid=(low+high)/2;
	}
	//注意不是四舍五入
	//注意当mid=5.00000时,(double)((int)(mid*100.0))/100.0可能为4.99，因此要加0.001
	mid=(double)((double)((int)(mid*100.0+0.001))/100.0);
	printf("%.2lf\n",mid);
}

int main()
{
	int num,i;
	double k;
	scanf("%d %lf",&num,&k);
	for(i=1;i<=num;i++) scanf("%lf",&len[i]);
	solve(num,k);
}