【NOI】荷马史诗

追逐影子的人，自己就是影子 ——荷马

Allison最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 w[i] 。Allison想要用 k 进制串 s[i] 来替换第 i 种单词，使得其满足如下要求：

对于任意的 1<=i,j<=n ， i<>j ，都有： s[i] 不是 s[j] 的前缀。

现在Allison想要知道，如何选择 s[i] ，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison还想知道最长的 s[i] 的最短长度是多少？

一个字符串被称为 k 进制字符串，当且仅当它的每个字符是 0 到 k-1 之间（包括 0 和 k−1 ）的整数。

字符串 Str1 被称为字符串 Str2 的前缀，当且仅当：存在 1<=t<=m ，使得 Str1 = Str2[1..t] 。其中， m 是字符串 str2 的长度， str2[1..t] 表示 str2 的前 t 个字符组成的字符串。

输入描述 Input Description

输入文件的第 1 行包含 2 个正整数 n,k ，中间用单个空格隔开，表示共有 n 种单词，需要使用 k 进制字符串进行替换。

接下来 n 行，第 i+1 行包含 1 个非负整数 w[i] ，表示第 i 种单词的出现次数。

输出描述 Output Description

输出文件包括 2 行。第 1 行输出 1 个整数，为《荷马史诗》经过重新编码以后的最短长度。第 2 行输出 1 个整数，为保证最短总长度的情况下，最长字符串 s[i] 的最短长度。

题目简述

k-进制哈夫曼编码

题解

容易得到每次都是选取最小的k个合并，如果大小相同，要选取编码长度短的

开始要先把一些合并起来，才能使答案最优，原因就不赘述了

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<string>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<queue>

#include<map>

#include<vector>

#include<set>

#define il inline

#define re register

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

using namespace std;

const int N=;

typedef long long ll;

int n,k,hs;

struct data{int w;ll v;} h[N];

il ll read(){

    re ll hs=;re char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)){

        hs=(hs<<)+(hs<<)+c-'';

        c=getchar();

    }

    return hs;

}

il bool cmp(re data a,re data b){

    return (a.v==b.v)?(a.w<b.w):(a.v<b.v);

}

il void swim(re int p){

    re int q=p>>;re data a=h[p];

    while(q>&&cmp(a,h[q])){

        h[p]=h[q];p=q;q=p>>;

    }

    h[p]=a;

}

il void sink(re int p){

    re int q=p<<;re data a=h[p];

    while(q<=hs){

        if(q<hs&&cmp(h[q+],h[q])) q++;

        if(cmp(a,h[q])) break;

        h[p]=h[q];p=q;q=p<<;

    }

    h[p]=a;

}

il void insert(re data v){

    h[++hs]=v;swim(hs);

}

il void pop(){

    h[]=h[hs--];sink();

}

int main(){

    n=read();k=read();

    for(int i=;i<=n;i++){

        h[i].v=read();

        h[i].w=;

    }

    sort(h+,h+n+,cmp);hs=n;

    re ll ans=,cnt=;

    re int maxn;

    if((n-)%(k-)>){

        for(int i=;i<=(n-)%(k-)+;i++){

            cnt+=h[].v;

        //    print();

            pop();

        }

        insert((data){,cnt});

        ans=cnt;

    }

    while(hs>){

        cnt=;maxn=;

        for(int i=;i<=k;i++){

            cnt+=h[].v;

            maxn=max(maxn,h[].w);

            pop();

        //    print();

        }

        insert((data){maxn+,cnt});

    //    print();

        ans+=cnt;

    }

    cout<<ans<<endl<<h[].w-<<endl;

    return ;

}

巴特西

【NOI】荷马史诗

题目简述

题解

最新文章

热门文章