【NOI】荷马史诗

【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 = ] 。其中， m 是字符串 str2 的长度， ] 表示 str2 的前 t 个字符组成的字符串。

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

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

输出文件包括 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=100001;
typedef long long ll;
int n,k,hs;
struct data{int w;ll v;} h[N];
il ll read(){re ll hs=0;re char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)){hs=(hs<<3)+(hs<<1)+c-'0';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>>1;re data a=h[p];while(q>0&&cmp(a,h[q])){h[p]=h[q];p=q;q=p>>1;}h[p]=a;
}
il void sink(re int p){re int q=p<<1;re data a=h[p];while(q<=hs){if(q<hs&&cmp(h[q+1],h[q])) q++;if(cmp(a,h[q])) break;h[p]=h[q];p=q;q=p<<1;}h[p]=a;
}
il void insert(re data v){h[++hs]=v;swim(hs);
}
il void pop(){h[1]=h[hs--];sink(1);
}
int main(){n=read();k=read();for(int i=1;i<=n;i++){h[i].v=read();h[i].w=1;}sort(h+1,h+n+1,cmp);hs=n;re ll ans=0,cnt=0;re int maxn;if((n-1)%(k-1)>0){for(int i=1;i<=(n-1)%(k-1)+1;i++){cnt+=h[1].v;//    print();
            pop();}insert((data){2,cnt});ans=cnt;}while(hs>1){cnt=0;maxn=0;for(int i=1;i<=k;i++){cnt+=h[1].v;maxn=max(maxn,h[1].w);pop();//    print();
        }insert((data){maxn+1,cnt});//    print();ans+=cnt;}cout<<ans<<endl<<h[1].w-1<<endl;return 0;
}

转载于:.html