哈夫曼树

CodeForces 226 B Naughty Stone Piles

Posted on

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

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

题意:
有几堆石头,要你将他们堆成一堆。两堆石头堆成一堆的花费是石头堆较小的石头数量。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;
}
哈夫曼树

哈夫曼编码

Posted on

传送门

OJ小作业 很久以前第一次听说哈夫曼树问了一下煞笔室友 听他很不屑地说 只是一个贪心而已 我也就没怎么在意

最近李总上课点名不得不去上一下 可惜也只是到那里发了一下呆 点了一下到就过去了 他在讲哈夫曼编码的时候我也没去听

搞得我刚开始看到这题的时候有点小蒙蔽 还好数据比较水 不然估计要卡很长时间 (因为完全是我根据以前的知识xjb搞的 还好还好是一A

下面是源码+注解 (因为完全是自己看了远离后搞得 可能有点烦........

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

#define root tree[id]
#define leson tree[ldir]
#define rison tree[rdir]

using namespace std;
const int maxn = 104;
int len, all_time;
int tree_root;//根节点
char to_c[maxn];//由节点的值转化为字符
char tar[maxn * 100];
char tar_ch;//当前目标字符
char output[maxn];//输出数组
bool flag;//标记  如果已经输出就直接返回

struct node {
    int lson, rson;
    int tim;//结点生成时间  所有原结点初始化为0
    int order;//节点编号
    int val;//结点的值
    bool operator<(const node& a) const
    {
        if (val != a.val)
            return val > a.val;
        if (tim != a.tim)
            return tim > a.tim;
        return order > a.order;
    }//按照题意出队
};

priority_queue<node> que;
node tree[maxn << 2];

int CreatTree()
{
    node ta, tb;
    int id;
    while (que.size() > 1) {
        ta = que.top();
        que.pop();
        tb = que.top();
        que.pop();
        id = len + all_time;
        root.lson = ta.order;
        root.rson = tb.order;
        root.val = ta.val + tb.val;
        root.order = id;
        root.tim = all_time++;
        que.push(root);
        // printf("%d %d\n",ta.order,tb.order);
    }//取出两个节点并合并再入队   最后剩余的便是根节点
    ta = que.top();
    que.pop();
    return ta.order;
}

void lock(int id, int dep)
{
    if (flag)//若已经输出过了   就直接返回
        return;
    int ldir = root.lson, rdir = root.rson;
    if (ldir) {
        output[dep] = '0';
        lock(ldir, dep + 1);
    }
    if (rdir) {
        output[dep] = '1';
        lock(rdir, dep + 1);
    }
    if (!ldir && !rdir && to_c[root.order] == tar_ch) {  //确保该结点为叶子结点也可以省点时间
        for (int i = 0; i < dep; i++)
            putchar(output[i]);
        flag = true;//标记为true
    }
}

int unlock(int index)
{
    int id = tree_root;
    while (root.lson || root.rson) {
        if (tar[index] == '0')  // 0 向左 1向右
            id = root.lson;
        else
            id = root.rson;
        index++;
    }
    putchar(to_c[root.order]);
    return index;//返回转化后的index
}

int main()
{
    while (scanf("%s", to_c + 1) != EOF) {
        len = strlen(to_c + 1);
        for (int id = 1; id <= len; id++) {
            scanf("%d", &root.val);
            root.order = id;
            root.tim = 0;
            root.lson = root.rson = 0;
            que.push(root);
        }
        all_time = 1;
        tree_root = CreatTree();
        // printf("root: %d\n",tree_root);
        // for(int id=1;id<=tree_root;id++)
        //    printf("order: %d  val: %d  lson: %d  rson:%d\n",root.order,root.val,root.lson,root.rson); //可取消注释查看建树是否正确
        scanf("%s", tar);
        int tar_len = strlen(tar);
        for (int i = 0; i < tar_len; i++) {
            tar_ch = tar[i];
            flag = false;
            lock(tree_root, 0);
        }
        puts("");
        scanf("%s", tar);
        tar_len = strlen(tar);
        int i = 0;
        while (i < tar_len)
            i = unlock(i);
        puts("");
    }
    return 0;
}