yukicoder No.67 よくある棒を切る問題 (1)

問題はこちら
No.67 よくある棒を切る問題 (1) - yukicoder

「ある長さxの棒をK本つくれるか？」という問題には
ΣLi/x　がK以上か否かを見ることで簡単に答えることができる
これを用いて2分探索をする

int main(){
	int a[200010],i,t,n;
	long k,s;
	double u=1e9,d=1e-9,m;
	//Liのmaxが1e9なので初期最大値は1e9でよい
	//また要求誤差が絶対誤差で1e-9なので初期最小値は1e-9で十分
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+i);
	scanf("%ld",&k);
	for(t=0;t<99;t++){
	//u-dの初期値が1e9くらいなので、2分探索は60回くらいやれば1e-9くらいの誤差になる
	//終了条件をu-dの値にするのはちょっと怖い
		m=(u+d)/2;
		s=0;
		for(i=0;i<n;i++)s+=a[i]/m;
		if(s>=k)d=m;else u=m;
	}
	printf("%.9f",u);
	return 0;
}

読み込みを1つにまとめたい

double u=1e9,d=1e-9,m;
long k,s,a[1<<18],i;
main(t){
	for(;~scanf("%ld",&s);k=s)a[~i--]=k;
	//Kの値を配列にいれてしまわないようワンクッション
	for(;t++<99;s>k?d=m:(u=m))for(s=i=1;a[i];s+=a[i++]/m)m=(u+d)/2;
	//sの初期値を1にしたので、条件もs>=kからs>kになっている
	i=!printf("%.9f",u);
}

170B