yukicoder : No.68 よくある棒を切る問題 (2)

当初☆２個だったけど自力で解けなかった…。
http://yukicoder.me/problems/146

問題

長さL[i]の棒がN本ある。

ここでQ個のクエリK[i]が与えられる。
N本の棒を分割して同じ長さの棒をK[i]本作る場合、長さの最大値を求めよ。
(クエリ間で分割状況は毎回リセットされる)

解法

Editorialを参考に解いた。

クエリ数が少ないならNo.67のように二分探索で求めればよいが、クエリ数が多いので二分探索では間に合わない。
クエリの上限K[i]は5*10^5である事を用いて、1本～5*10^5本の場合を全部求めておこう。

PriorityQueueを用いて各棒において「もう１個多くに分割する場合、長さはどうなるか」を管理し、その長さが最大となる棒を選んで分割数を増やしていけば良い。

int N,Q;
ll L[300000];
int num[500005];
double res[500005];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	priority_queue<pair<double,int> > P;
	
	FOR(i,N) cin>>L[i], P.push(make_pair(L[i],i));
	
	for(i=1;i<=500000;i++) {
		res[i] = P.top().first;
		j=P.top().second;
		P.pop();
		num[j]++;
		P.push(make_pair(L[j]/(num[j]+1.0),j));
	}
	
	cin>>Q;
	while(Q--) cin>>x, _P("%.12lf\n",res[x]);
}

まとめ

勉強になりました。