题目链接：https://www.luogu.com.cn/problem/P2168 题目大意：存在从1 ~ n的n个数，给定每个数出现的次数times[i]，现在想用一个k进制数来替换数字i，希望最后得到的字符串s的长度最小。求出s的最小长度以及1 ~ n中在k进制下最长的数的长度是多少。 题目分析： 1.看完题目我们就应该明白，应该让使用次数越多的数的长度越短，这样才能达到使k进制下s最短的目的。 2.很明显，当我们把times[i]当作权值w[i]，把k进制数表示数字i的结果表示为字典树，每个数被替换后的长度l[i]就是树的根节点到叶子节点的距离，那么这个题就转化为了标准的Huffman树的题目了。 3.此时w[i]*l[i]就是最终在字符串s中，由数字i转化出来的长度。所以答案是要求就是使得∑w[i]*l[i]最小，而答案就是Huffman树最后的树根中的值。 4.由于此题不需要我们得到具体的编码，所以不需要手写一个Huffman树，我们只需要用优先队列priority_queue来模拟就可以了。 5.因为答案还要求了最长数的长度，根据字典树的性质我们知道，显然最长数的长度就是离根节点最远的点到根节点的边数。所以我们只需要在优先队列中同时保存一下从该子树最远的叶子节点到子树树根的距离就可以了。 正解程序：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> using namespace std; typedef long long ll; struct node { ll val; ll depth; bool operator<(const node a)const { if(val!=a.val) return val>a.val; return depth>a.depth; } }; priority_queue<node,vector<node>,less<node> > s; ll n,k; int main() { scanf("%lld%lld",&n,&k); for(ll i=1;i<=n;i++) { node num; scanf("%lld",&num.val); num.depth=0; s.push(num); } while((n-1)%(k-1)) { n++; node num; num.val=num.depth=0; s.push(num); } ll ans=0; while(s.size()!=1) { ll temp=0,h=0; for(ll i=1;i<=k;i++) { node now=s.top(); temp+=now.val; h=max(h,now.depth); s.pop(); } ans+=temp; node num; num.val=temp; num.depth=h+1; s.push(num); } printf("%lld\n%lld\n",ans,s.top().depth); return 0; }