ネズミ匹

時間制限:1秒メモリ制限:64 M
Description
n個のボトルがあり、そのうち1個しかない飲料が有毒であることが知られている.今、どの瓶の飲み物が毒があるか知りたいので、マウスを探してテストをしました.
もし私たちが十分なマウスを持っているとしたら、テスト速度を速めるために、私たちは毎回いくつかの瓶からのテストサンプルを混ぜて、マウスに与えることができます.もしマウスが毒のある飲み物を飲んだら、死んでしまいます.
今、瓶ごとの飲み物に毒がある確率(といつも100%)をあげて、最適な戦略(テスト回数はできるだけ少ない)で実行して、所望のテスト回数はいくらですか?
Input
第1の動作データ群数T(T<=20)を入力する.
各セットのデータについて、最初は空行であり、次の第1の挙動ボトルの個数n(1<=n<=100)である.次の動作nの実数p 1...pnは、各ボトル中の飲料が有毒である確率を示す(sum{pi|1<=i<=n}=1).
Output
各セットのデータに対して1つの数を出力し、所望のテスト回数のために、小数点後に2桁の数字を保持します.
Sample input
3
3
0.5 0.25 0.25
4
0.25 0.25 0.25 0.25
2
0.00 1.00
Sample output
1.50
2.00
1.00
Hint
確率が0のイベントは必ずしも不可能なイベントではありません.例えば、数軸上でランダムに点を選択し、結果的に全点を選択します.
だから3組目のサンプルは一度測定する必要があります.
参考の偉神blog:http://blog.csdn.net/zhangwei1120112119/article/details/8549066

zhangwei 11212119のコラム

BIT 1020マウス
最初に偉神のblogを見たとき、なぜハフマンの木なのか分からなかったので、私は自分の考えで解いた:まず直接降順して並べた後、1からnまで、あなたのマウスの確率を使って、計算した結果が間違っていて、元の薬物が混合して使うことができることを発見して、一瞬にして最良の二叉樹で解くことができることを理解して、それから優先列で直接この問題を撮りました.Cには優先単調キューがサポートされていないので、私は1つのキューを使って、操作が終わるたびに、一度速く並べて、優先単調キューを形成しました.

#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a,const void *b){

	return (*(double *)a) > (*(double *)b)?-1:1;
}

int main(){
	int T;// T <= 20
	int n; // n <= 100, 
	int i;
	double priority_Q[120],ans;

	scanf("%d",&T);
	
	while(T--){
		scanf("%d",&n);
		for(i = 0; i < n; ++i){
			scanf("%lf",&priority_Q[i]);
		}
		ans = 0.0;
		while(n!=1){
			qsort(priority_Q,n,sizeof(double),cmp);
			ans += priority_Q[n-2] + priority_Q[n-1];
			priority_Q[n-2] +=  priority_Q[n-1]; ;
			--n;
		}

		printf("%.2lf
",ans);
	}
	return 0;
}