Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needsN(1 ≤N≤ 20,000) planks of wood, each having some integer lengthLi(1 ≤Li≤
50,000) units. He then purchases a single long board just long enough to saw into theNplanks (i.e., whose length is the sum of the lengthsLi). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made;
you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of theN-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create theNplanks. FJ knows that he can cut the board in various different orders which will
result in different charges since the resulting intermediate planks are of different lengths.
Input
Line 1: One integerN, the number of planks
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank
Output
Line 1: One integer: the minimum amount of money he must spend to makeN-1 cuts
Sample Input
3
8
5
8
Sample Output
34
很自然的想到的哈夫曼树(贪心策略).
但是怎么样排序有效率呢? 每次只是取出两个最小的,然后再相加,再放进去,再排序。
经过测试,普通的排序会超时。
下面代码运行正确,但是超时. 主要是sort 函数太费时了,因为每次排序只是插入一个数而已。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int64;
int len;
int64 arr[20001];
int main() {
while (cin >> len) {
for (int i = 0; i < len; i++) {
cin >> arr[i];
}
int tmplen = len;
int sum = 0;
sort(arr + (len - tmplen), arr + len);
while (tmplen > 1) {
sort(arr + (len - tmplen), arr + len);
arr[len - tmplen + 1] = arr[len - tmplen] + arr[len - tmplen + 1];
sum += arr[len - tmplen + 1];
tmplen--;
}
cout << sum << endl;
}
return 0;
}
由于只是插入一个数。下面自己写插入排序:
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int64;
int len;
int64 arr[20001];
int main() {
while (cin >> len) {
for (int i = 0; i < len; i++) {
cin >> arr[i];
}
int index = 1;
int64 sum = 0,temp;
sort(arr, arr + len);
while (index < len-1) {
temp = arr[index-1] + arr[index];
int i;
for(i=index + 1; i<len; i++){
if(temp < arr[i]){ //插入完成退出循环
arr[i-1] = temp;
break;
}else
arr[i-1] = arr[i];
}
if(i==len) //如果遍历到了最后,也没插入
arr[i-1] = temp;
index++;
sum += temp;
}
sum += arr[len-1] + arr[len-2]; //把剩余的两个数加上
cout << sum << endl;
}
return 0;
}
运行时间 550ms
算是勉强通过。
下面写更高效的堆排序,小顶推。
#include <iostream>
using namespace std;
typedef long long int64;
int len;
int64 arr[20001]; //arr[0] 存数当前数组的长度
//调整堆
void heap(int i) {
int left = i * 2;
int right = i * 2 + 1;
int mins = i;
if (left <= arr[0] && arr[left] < arr[mins])
mins = left;
if (right <= arr[0] && arr[right] < arr[mins])
mins = right;
if (i != mins) {
swap(arr[i], arr[mins]);
heap(mins);
}
}
//想堆中插入一个数
void inheap(int64 key) {
arr[++arr[0]] = key;
int64 i = arr[0];
//i就是当前插入的最后位置. 循环 lgn 次即可
while (i > 1 && arr[i] < arr[i / 2]) {
swap(arr[i], arr[i / 2]);
i = i / 2;
}
}
//返回最小的两个数的和
int64 get() {
int64 p = arr[1], q;
arr[1] = arr[arr[0]]; //第一个位置 和 最后一个位置交换
arr[0]--; //数组长度减1
heap(1); //调整位置1
q = arr[1];
arr[1] = arr[arr[0]];
arr[0]--;
heap(1);
inheap(p + q); //返回最小的两个数的和
return p + q;
}
int main() {
while (cin >> len) {
arr[0] = 0;
for (int i = 1; i <= len; i++) {
cin >> arr[i];
inheap(arr[i]);
}
int64 ans = 0;
for (int i = 1; i < len; i++) {
ans += get();
}
cout << ans << endl;
}
return 0;
}
运行时间70ms
分享到:
相关推荐
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上; 2.利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入...
哈夫曼树构造 输出
哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2哈夫曼树编码哈夫曼树2
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树
1)哈夫曼树类型、select()函数(求两最小权值结点)、哈夫曼树构建、求编码函数、字符串输入处理函数等的声明放在huffman.h文件; 2)select()函数、哈夫曼树构建、求编码函数的实现可放在huffman.c文件; 3)输入...
这是我做的一个基于哈夫曼树思想的压缩算法程序源码,希望大家指正
本资源是数据结构中利用最小堆实现哈夫曼树的一个C++代码,仅供参考,欢迎指正
printf("请输入树叶子结点的总数:"); scanf("%d",&n); t=2*n-1; printf("请输入各叶子结点的数值:"); for(j=1;j;j++) {scanf("%d",&r[j].data); r[j].tag=0; r[j].lch=0; r[j].rch=0; } i=0; while(i) {...
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int num)//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if...
首先根据给定的n个字符的权值构造哈夫曼树。通过遍历此二叉树完成各字符的哈夫曼编码,另输入一组‘0’、‘1’代码构成的报文将其翻译成对应的字符信息。
C语言实现的哈夫曼树
数据结构课程设计:哈夫曼树及其应用 文档 ++代码 构建哈夫曼树,编码,译码
数据结构哈夫曼树PPT学习教案.pptx
c++ 源代码 哈夫曼树 哈夫曼编码 部分代码如下: #include"Huffman.h" #include"hfmTree.h" #include using namespace std; int main() { cout~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~...
构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
上机后的代码,内容为构建哈夫曼树,并求最短编码长度。
根据输入的权值建立一棵哈夫曼树,并显示该树的结点序号、双亲结点、左/右孩子结点以及各结点所对应的哈夫曼编码。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并以直观的方式(比如树)显示在终端上;