TopCoder SRM 768 : Div1 Easy MeanMedian

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で解いた人もいたようで。