题目描述
追逐影子的人,自己就是影子。 ——荷马
Allison 最近迷上了文学。她喜欢在一个慵懒的午后,细细地品上一杯卡布奇诺,静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了,Allison 想通过一种编码方式使得它变得短一些。
一部《荷马史诗》中有种不同的单词,从
到
进行编号。其中第
种单词出现的总次数为
。Allison 想要用
进制串
来替换第
种单词,使得其满足如下要求:
对于任意的,
,都有:
不是
的前缀。
现在 Allison 想要知道,如何选择,才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下,Allison 还想知道最长的
的最短长度是多少?
一个字符串被称为进制字符串,当且仅当它的每个字符是
到
之间(包括
和
)的整数。
字符串被称为字符串
的前缀,当且仅当:存在
,使得
。其中,
是字符串
的长度,
表示
的前
个字符组成的字符串。
输入格式
输入文件的第行包含
个正整数
,中间用单个空格隔开,表示共有
种单词,需要使用
进制字符串进行替换。
接下来行,第
行包含
个非负整数
,表示第
种单词的出现次数。
输出格式
输出文件包括 2 行。
第行输出
个整数,为《荷马史诗》经过重新编码以后的最短长度。
第行输出
个整数,为保证最短总长度的情况下,最长字符串
的最短长度。
题目解析
NOI的难度真是越来越接近NOIP了。
观察题目性质,与Huffman树的构造方式非常相似。这启发我们借鉴Huffman树的思想来解决本题。
首先解决第一个子问题。若,那就和普通的Huffman树构造基本一样,即每次选取权值最小的
棵子树,新建一个结点
作为它们在树上的父亲,并将
的权值赋为这
棵子树的和。若
,也比较容易解决,我们要保证权值大的深度尽量小,那就先选取
个权值最小的结点,就将问题转化成上面一种情况了。
再来考虑第二个子问题。如何保证串长最短?也就是保证Huffman树的高度最小。我们在选取权值最小的个结点时,相同权值的情况下应贪心地选取子树高度最大的。这样就可以满足第二个子问题的要求了。
总时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
/************************************************************** Problem: 4198 User: frank_c1 Language: C++ Result: Accepted Time:968 ms Memory:9052 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to; }; struct node { int x; LL v; node(int a=0,LL b=0):x(a),v(b) {} }; bool operator < (node a,node b) { if(a.v!=b.v) return a.v>b.v; return a.x>b.x; } const int maxn=(int)(2e5)+5; int fr[maxn]; edge e[maxn<<1]; LL val[maxn]; int tote=0,idx=0; inline void addedge(int u,int v) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].to=v; } priority_queue<node> Q; int mx=0; LL tot=0; void dfs(int x,int d) { bool c=1; RAL(i,x) { c=0; dfs(e[i].to,d+1); } if(c) mx=max(mx,d),tot+=val[x]*d; } int main() { int n,k; read(n);read(k); memset(fr,-1,sizeof(fr)); REP(i,1,n) { read(val[i]); Q.push(node(i,val[i])); } int cnt=n;idx=n; while(cnt>1) { node w;w.x=++idx; int p=0; if((cnt-1)%(k-1)!=0) p=(cnt-1)%(k-1)+1; else p=k; REP(i,1,p) if(cnt>0) { node c=Q.top();Q.pop(); addedge(idx,c.x); w.v+=c.v;cnt--; } Q.push(w);cnt++; } dfs(idx,0); printf("%lld\n%d\n",tot,mx); return 0; } |