UOJ#130 【NOI2015】荷马史诗 K叉哈夫曼树
2024-10-21 06:20:27
【NOI2015】荷马史诗
因为不能有前缀关系,所以单词均为叶子节点,就是K叉哈夫曼树。第一问直接求解,第二问即第二关键字为树的高度。
#include< cstdio >
#include< algorithm > typedef unsigned long long ull;
template
inline void read(T&x)
{
x=0;bool f=0;char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar(); if(c=='-')f=1,c=getchar();
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x=f?-x:x;
}
const int MAXN(100010);
struct Data
{
ull val;int dep;
inline bool operator <(const Data &A)const {return (val==A.val)?dep>A.dep:val>A.val;}
}h[MAXN],New;int top;
int n,k,First;ull Ans,sum,w[MAXN];
void umax(int &a,int b){if(a<b)a=b;}
int main()
{
// freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
read(n);read(k);
for(int i=1;i<=n;i++)read(w[i]),sum+=w[i];
for(int i=1;i<=n;i++)h[++top]=(Data){w[i],1};
std::make_heap(h+1,h+1+top);
First=(n-1)%(k-1) +1;
// printf("%d\n",First);
// printf("%llu\n",sum);
if(First>1||n==1)
{
for(int i=1;i<=First;i++)
{
New.val+=h[1].val;
Ans+=h[1].val;
umax(New.dep,h[1].dep);
std::pop_heap(h+1,h+1+top);top--;
}
New.dep++;h[++top]=New;
std::push_heap(h+1,h+1+top);
}
while(top>1)
{
New.val=New.dep=0;
for(int i=1;top&&i<=k;i++)
{
New.val+=h[1].val;
Ans+=h[1].val;
umax(New.dep,h[1].dep);
std::pop_heap(h+1,h+1+top);top--;
}
New.dep++;
// printf("%llu %d\n",New.val,New.dep);
h[++top]=New;
std::push_heap(h+1,h+1+top);
}
printf("%llu\n",Ans);
printf("%d\n",h[1].dep-1);
return 0;
}
最新文章
- Jenkins配置MSBuild实现自动部署(MSBuild+SVN/Subversion+FTP+BAT)
- java实现敏感词过滤(DFA算法)
- [LeetCode] Spiral Matrix 螺旋矩阵
- jQuery extend扩展String原型
- css3动态旋转魔方练习
- 深入了解try catch
- xampp3.2下mysql中文乱码终极解决方案
- SqlDataAdapter类
- HTML相关知识
- [AHOI2004]奇怪的字符串
- Hbase出现ERROR: Can&#39;t get master address from ZooKeeper; znode data == null正确找到解决思路
- PL/SQL学习笔记之函数
- 关于ICO的一些理解
- Yii2 Apache + Nginx 路由重写
- POJ 2393
- 微信小程序 - 自定义tabbar
- day21<;IO流+&;FIle递归>;
- Docker - CentOS 安装 Docker 和 Docker-Compose
- 滚动数组要来回赋初值呀。。orzzzzzzzzzzzzzzzzzzzzzzzzzz
- 图形数据库(GraphDB)