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': ' '); } }