SRM536 Div1 Easy - MergersDivOne

問題

会社がn社あり、i番目の収入はr[i]である
2個以上の会社を併合してできた会社の収入はそれらの会社の元の収入の平均になる
最後に1社だけ残るまでうまく併合していったときにできる会社の収入の最大値を求めよ

解法

収入の昇順にソートし、先頭の2社を併合し続けるのが最善
これは推測しやすいしeditorialにも簡単に証明できると書いてある
けど疲れてるせいか証明が全くできないのでまた今度します

class MergersDivOne {
public:
	double findMaximum(vector<int> r) {
		sort(all(r));
		double res = r[0];
		reps(i,1,r.size()) res = (res + r[i])/2;
		return res;
	}
};