もったいない…
http://community.topcoder.com/stat?c=problem_statement&pm=14936
問題
数列が与えられる。
連続した部分列を選択すると、それらが平均値で置き換わる処理を任意回数行えるとする。
そうして生成できる数列のうち、辞書順最小のものを求めよ。
解法
辞書順最小なので、数列の先頭から順に、その要素を左端とし、平均値が最小となる右端を探して平均値に置き換える処理を繰り返そう。
最小値となる右端候補が複数あっても問題ない。
class SubarrayAverages { public: vector <double> findBest(vector <int> arr) { int N=arr.size(); vector<double> V; int i,j; FOR(i,N) V.push_back(arr[i]); FOR(i,N) { int best=i; double av=V[i]; double t=V[i]; for(j=i+1;j<N;j++) { t+=V[j]; if(t/(j-i+1)<av) { av=t/(j-i+1); best=j; } } for(j=i;j<=best;j++) V[j]=av; } return V; } } *まとめ
