Codeforces Round #140 (Div. 1) B : Naughty Stone Piles

問題概要

山がN(<10^5)個あり、各山には石がA[i]個ある。どれか山を選んで別の山に移動する。このとき移動した分の個数のコストがかかる。ある山に別の山をマージするのは高々K回までしかできない。最小コストを各Kについて求める問題。

解法

問題をほどくと、K分木の頂点に番号を降って(深さ*値)の和を最小化する問題だと読み替えられる。こう読み替えるともう解けたも同然で、自明に貪欲が最適となる。

acceptされたコード

キャッシュするのであればK=1を特別扱いする必要はなかった。

const int MAX_N = int(1e5);
const int MAX_Q = int(1e5);

int N, Q;
int qs[MAX_Q], as[MAX_N];
int64 accum[MAX_N + 1];
int64 memo[MAX_N + 1];

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}
	scanf("%d", &Q);
	for (int i = 0; i < Q; ++i) {
		scanf("%d", qs + i);
	}
}

int64 subSolve(int k) {
	if (memo[k]) {
		return memo[k];
	}
	if (k == 1) {
		int64 ans = 0, d = 0;
		for (int i = 0 ;i < N; i++, ++d) {
			ans += int64(as[i]) * d;
		}
		return memo[k] = ans;
	}
	int64 cur = 0, base = 1, ans = 0, d = 0;
	for (; cur < N; ++d) {
		ans += d * (accum[min<int64>(cur + base, N)] - accum[cur]);
		cur += base;
		base *= k;
	}
	return memo[k] = ans;
}

void solve() {
	sort(as, as + N, greater<int>());
	for (int i = 0; i < N; ++i) {
		accum[i+1] = accum[i] + as[i];
	}
	for (int i = 0; i < Q; ++i) {
		printf("%lld%c", subSolve(qs[i]), i == Q-1 ? '\n': ' ');
	}
}