問題
http://community.topcoder.com/stat?c=problem_statement&pm=11799&rd=14728
複数の会社が与えられる。
そのうち任意の数を選択し、その価値の和／選択した数が合併した後の価値になる。
すべての会社を合併した時、最大となる価値を求める。
解き方
最初の数の順番は回答に関係しないので昇順にソート。
このとき、すべての点をプロットすると、２つずつ左から合併を繰り返した方がよいことがわかる。
（合併後の点が順に右に移動していく。仮に３つを選択した時はその中間になり間の値があまり意味を持たないため、２つずつがよいことがわかる）
コード
class MergersDivOne {
public: double findMaximum(vector<int> revenues) {
sort(revenues.begin(),revenues.end());
double ans=revenues[0];
FORE(i,1,revenues.size())ans=(ans+revenues[i])/2.0;
return ans;
}
};
public: double findMaximum(vector<int> revenues) {
sort(revenues.begin(),revenues.end());
double ans=revenues[0];
FORE(i,1,revenues.size())ans=(ans+revenues[i])/2.0;
return ans;
}
};