EasyとMediumがまぁまぁの速度で解けて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=15557
問題
N要素(奇数)の数列があり、各要素0~10の値を取れる。初期値は0である。
i番目の要素は、コストD[i]かけて1加算できるものとする。
数列に対し平均値Mean・中間値Medianを達成できるようにするのに必要な最少総コストを求めよ。
解法
当然ながらD[i]の小さい順に1加算していくのが基本方針である。
よってDをソートしておこう。
まず中間値の条件を満たすため、先頭(N+1)/2要素をまずMedianずつ加算しよう。
平均の条件を満たすには、総和がMean*Nを超えればどこに加算してもよいので、10を超えない範囲でD[i]の小さい順に加算を繰り返せばよい。
class MeanMedian { public: int minEffort(int needMean, int needMedian, vector <int> d) { int N=d.size(); sort(ALL(d)); int ret=0; needMean*=N; vector<int> V; int i,j; FOR(i,N) { if(i<N/2+1) { ret+=needMedian*d[i]; needMean-=needMedian; FOR(j,10-needMedian) V.push_back(d[i]); } else { FOR(j,10) V.push_back(d[i]); } } sort(ALL(V)); FOR(i,needMean) ret+=V[i]; return ret; } }
まとめ
これは大して迷わなかった。
DPで解いた人もいたようで。