Safe Or Unsafe
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1239 Accepted Submission(s): 484
/* 题意:就是给你一个字符串如:12 helloworld统计出其中d:1个,e:1个,h:1个,l:3个,o:2个,r:1个,w:1个,
然后用一个数组保存起来a[7]={1,1,1,1,1,2,3};然后就是用哈夫曼树的思想求出新建的非叶子节点的权值之和:sum与12相比较
如果sum小于等于12的话就输出yes否则输出no,此案例求出的sum=27;所以输出no。
思路:按照建立哈夫曼树的思路每次求出两个的权值用min1保存最小的,min2保存次小的,
然后(min1+min2)加入其中,但是min1和min2需要踢出去,此题我用优先队列做的,就是
每次弹出最小的(min1)和次小的(min2),然后把(min1+min2)压入队列中。//题中a=min1;b=min2;
但是有一组很坑爹的测试数据,开始的时候一直错,5 aaaaa 输出的是yes,5 aaaaaa输出的是no*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std; priority_queue<int, vector<int>, greater<int> >Q;//从小到大,优先队列 char str[];
int huf[];
int n; void solve()
{
int ans=;
int a,b;
while(Q.size()!=)
{
a=Q.top();//优先队列区最小的数(认为已经排好顺序了)
Q.pop();
b=Q.top();
Q.pop();
Q.push(a+b);//把新的根入队;
ans+=(a+b);//本题要求的权值;
}
printf(ans<=n?"yes\n":"no\n");
} int main()
{
int T,i,len;
scanf("%d",&T);
while(T--)
{
while(!Q.empty())//保证队列为空
Q.pop();
memset(huf,,sizeof(huf));
scanf("%d",&n);
scanf("%s",str);
len=strlen(str);
for(i=;i<len;i++)
{
huf[str[i]-'a']++;//统计各个字母的个数
}
for(i=;i<;i++)
if(huf[i])//如果有字母就入队
Q.push(huf[i]);
if(Q.size()==)//没有子叶的情况
{
int m=Q.top();
Q.pop();
printf(m<=n?"yes\n":"no\n");
}
else
solve(); }
return ;
}
我的一道树的题目,纪念一下我的入门,,,哈哈
下面是用哈弗曼树写的,有点麻烦;感觉还是优先队列模拟的好,不过也可以参考一下哈
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
int weight;
int parent,left,right;
};
char a[];
int huf(int str[],int size)
{
int i,lenth=*size,min1,min2,x,y,sum=,j;
struct node *hf;
hf=(struct node *)malloc(lenth*sizeof(struct node));//开创
for(i=size;i<lenth;i++)
{
hf[i].weight=str[i-size];
hf[i].parent=hf[i].left=hf[i].right=;
}
for(i=size-;i>;i--)
{
min1=min2=;
x=y=;
for(j=i+;j<lenth;j++)
{
if(min1>hf[j].weight&&hf[j].parent==)
{
min2=min1;
y=x;
min1=hf[j].weight;
x=j;
}
else if(min2>hf[j].weight&&hf[j].parent==)
{
y=j;
min2=hf[j].weight;
}
}
hf[i].weight=min1+min2;
sum=sum+hf[i].weight;
hf[i].parent=;
if(x>y)
swap(x,y);
hf[i].left=y;
hf[i].right=x;
hf[x].parent=i;
hf[y].parent=i;
}
return sum;
}
int main()
{
int T,n,i,j,len,num[],b[];
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
len=;
memset(b,,sizeof(b));
scanf("%d",&n);
getchar();
scanf("%s",a);
for(i=;a[i]!='\0';i++)
b[a[i]-'a']++;//把字母个数存入数组
for(i=;i<;i++)
if(b[i]!=)
num[len++]=b[i];//除去空字母
if(len==)
{
if(num[]<=n)
printf("yes\n");
else
printf("no\n");
}
else
{
if(huf(num,len)<=n)
printf("yes\n");
else
printf("no\n");
}
}
}
return ;
}
Safe Or Unsafe(hdu2527)哈弗曼VS优先队列的更多相关文章
-
hdu 2527 Safe Or Unsafe (哈夫曼树)
Safe Or Unsafe Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)To ...
-
HDU2527:Safe Or Unsafe(哈弗曼树)
Problem Description Javac++ 一天在看计算机的书籍的时候,看到了一个有趣的东西!每一串字符都可以被编码成一些数字来储存信息,但是不同的编码方式得到的储存空间是不一样的!并且当 ...
-
HDU-2527 Safe Or Unsafe
http://acm.hdu.edu.cn/showproblem.php?pid=2527 建哈夫曼树,哈夫曼编码,求wpl值. Safe Or Unsafe Time Limit: 2000/10 ...
-
SLT 优先队列 哈弗曼树最小带权路径
与普通的队列不同,普通的队列是先进先出的,而优先队列出队的顺序不是先进先出,而是大(或者小)元素先出队,需要#include <queue> 成员函数 成员函数 作用 empty() 判断 ...
-
hdu 2527:Safe Or Unsafe(数据结构,哈夫曼树,求WPL)
Safe Or Unsafe Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)To ...
-
hdu 2527 Safe Or Unsafe (优先队列实现Huffman)
Safe Or UnsafeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tot ...
-
K:哈弗曼树
相关介绍: 树形结构除了应用于查找和排序等操作时能调高效率,它在信息通讯领域也有着广泛的应用.哈弗曼(Huffman)树就是一种在编码技术方面得到广泛应用的二叉树,它同时也是一种最优二叉树. 哈弗曼 ...
-
POJ 3253 Fence Repair(简单哈弗曼树_水过)
题目大意:原题链接 锯木板,锯木板的长度就是花费.比如你要锯成长度为8 5 8的木板,最简单的方式是把21的木板割成13,8,花费21,再把13割成5,8,花费13,共计34,当然也可以先割成16,5 ...
-
POJ 1862 Stripies【哈夫曼/贪心/优先队列】
Stripies Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 18198 Accepted: 8175 Descrip ...
随机推荐
-
[Linux系统]查看内存的几种方式
1. cat /proc/meminfo 2.free -m3.vmstat -s4.ps命令可以实时的显示各个进程的内存使用情况.Reported memory usage information ...
-
IO流05--毕向东JAVA基础教程视频学习笔记
Day20 10 创建java文件列表11 Properties简述12 Properties存取13 Properties存取配置文件14 Properties练习15 PrintWriter16 ...
-
【转】3篇:Xilium CefGlue 关于 CLR Object 与 JS 交互类库封装报告:官方原生方法分析
作者: 牛A与牛C之间 时间: 2013-11-17 分类: 技术文章 | 暂无评论 | 编辑文章 主页 » 技术文章 » 第3篇:Xilium CefGlue 关于 CLR Object 与 JS ...
-
Android学习笔记--处理UI事件
Handling UI Events 在Android里, 有不只一种方式可以截获用户与你的应用程序交互的事件. 在你的界面上处理事件时,你需要捕获用户与某个View实例交互时所产生的事件.View类 ...
-
requestAnimationFrame之缓动的应用
之前需要使用的定时器的时,立马想到的是setInterval(),用着用着就成为习惯,并没有遇到什么不妥之处.习惯性的操作往往容易让一个人拒绝尝试一些其他的方法.现在的方法用得好好的,没事干啥找其他法 ...
-
[数]数学系列预习->;补水题ver.
---恢复内容开始--- 话说要学反演了,contest一题都搞不定,整理题目暂且搁置,数学笨蛋来学一下数学_(:з」∠)_ ---恢复内容结束--- 是的,预习看了半天教学,没有整理,做题又都不会, ...
-
Go语言使用Beego的ORM插入Mysql后,时区不一致的解决方案
一.解决方案: 方案一: orm.Debug = false orm.DefaultTimeLoc = time.UTC orm.RegisterDriver("mysql", o ...
-
20155338 ch02 ch03课下作业
20155338 ch02 ch03课下作业 要求: 1.补充完成课上测试(不能只有截图,要有分析,问题解决过程,新学到的知识点) 课上测试-3-ch02 1.编写一个程序 "week060 ...
-
[GitHub] git push的时候报错 fatal: unable to access &#39;http://github.com/xxx/xxx.git/&#39;: Recv failure: Connection reset by peer
参考了两种方法: 1. 解决fatal: unable to connect to github.com问题 http://blog.csdn.net/greenqingqingws/article/ ...
-
sql server时间戳timestamp
sql server时间戳timestamp 在SQL Server中联机丛书是这样说的: SQL Server timestamp 数据类型与时间和日期无关.SQL Server timestamp ...