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

★２から★３に後で格上げされた問題なので、★３の割に簡単。
http://yukicoder.me/problems/145

問題

N本の木材があり、i番目の長さはL[i]である。
これらの木材を任意に切り、同じ長さの木材をK本そろえたい。
(木材の連結はできない)

K本をそろえられる最長の木材の長さを求めよ。

解法

長さlが決まれば、sum(L[i]/l)で得られる数が容易に求められる。
よって長さで二分探索すればよい。

int N;
ll L[300000],K;

ll num(double v) {
	ll t=0;
	int i;
	FOR(i,N) t+=L[i]/v;
	return t;
}

void solve() {
	int i,j,k,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i];
	cin>>K;
	
	double l=0,r=1e11;
	double m;
	FOR(i,100) {
		m=(l+r)/2;
		if(num(m)>=K) l=m;
		else r=m;
	}
	_P("%.12lf\n",m);
}

まとめ

この回は(2)に関心したので、(1)は印象薄いのよね。