CodeForces 226 B Naughty Stone Piles

遇到的第二道哈夫曼树，这个哈夫曼树有些特别，当你将两个结点组合的时候，你只需要付出权值较小的花费。
简单说，结点权值组合的时候并不会产生新的结点！！
这就可以完全摒弃优先队列，直接用数组实现以求更为高效。

上次意外地发现两个队友都不会哈夫曼树……真是惊了……

题意：
有几堆石头，要你将他们堆成一堆。两堆石头堆成一堆的花费是石头堆较小的石头数量。q个询问，每次询问限制一堆石头，被其他石头合并的次数。

思路：
这道题，若是转化成图来说就是一个k叉哈夫曼树，然而不会产生新结点，也就是说所有结点的权值和位置都已经可以直接求得了。
将他降序排序，每次将同一层的权值乘以他的深度就是该层的花费。

注 : 下表很容易爆 int 自己想想很容易想到……
然而RE了好几发……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 5;
int n;
ll ans[maxn], sum[maxn], ary[maxn];

void solve(int q)
{
    ll dep = 1, idx = 1, nxt;
    ll tmp, res = 0, d = q;
    while (idx <= n) {
        nxt = idx + d <= n ? idx + d : n;
        tmp = sum[nxt] - sum[idx];
        res += tmp * dep;
        idx += d, dep++, d *= q;
    }
    printf("%lld ", ans[q] = res);
}

int main()
{
    int qn, q;
    scanf("%d", &n);
    range(i, 1, n) scanf("%lld", ary + i);
    sort(ary + 1, ary + 1 + n, greater<int>());
    range(i, 1, n) sum[i] = ary[i] + sum[i - 1];
    scanf("%d", &qn);
    while (qn--) {
        scanf("%d", &q);
        if (ans[q])
            printf("%lld ", ans[q]);
        else
            solve(q);
    }
    return 0;
}