|
Time Limit: 2000MS |
|
Memory Limit: 65536K |
|
Total Submissions: 19763 |
|
Accepted: 6269 |
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 theN planks (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 theN planks. 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
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
Hint
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into
16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).
Code:
又错了好多次...
第一次:
在存放权值的数组中每次都取最小的两个, 取过的标记为1, 下次不再访问, 两个相加依次放在数组下标从n+1到2*n-1的位置
(一开始是定义了一个结构体,元素有五个哪,后来发现双亲和孩子节点都没什么用,就给改成一维数组了)
结果当然是超时啊,啊啊啊啊
#include"stdio.h"
#include"stdlib.h"
int n,money=0;//要切n块木板,花money块钱
//typedef struct node
//{
// int weight;
// int parent,lchild,rchild;
//}node;
int huff[40010];
int sign[40010];//标志位,用以判断该元素是否被使用建立过
int bulid(int n)//建立一个具有n个叶子节点的哈弗曼树,
//实际上是一维数组,下标代表节点,该下标存的元素为权值
//建成后将n+1~2n-1的权值相加即为所求结果
{
money = 0;
int min1,min2,index1,index2;//表示第1小,第2小
int end = n+1;//end表示循环终止的位置,
//因为没选出两个最小的都要有一个新的结果出来,需+1
int i;
while(end<2*n)
{
index1 = index2 = 0;
min1 = min2 = 50001;//大于50000即可
for(i=1;i<end;i++)//寻找两个最小的数字
{
if(!sign[i])
{
if(huff[i]<min1)
{
min2 = min1;
index2 = index1;
min1 = huff[i];
index1 = i;
}
else if(huff[i]<min2)
{
min2 = huff[i];
index2 = i;
}
//printf("min1:%d min2:%d\n",min1,min2);
sign[index1] = sign[index2] = 1;
}
}
huff[end++] = min1 + min2;
//printf("%d:%d\n",end-1,huff[end-1]);
}
// printf("end%d\n",end);
for(i=end-1;i>n;i--)
money = money + huff[i];
return money;
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<2*n;i++)
sign[i] = 0;//标志位初始化
for(i=1;i<=n;i++)
scanf("%d",&huff[i]);//输入权值
if(n==0 || n==1) printf("0\n");
else printf("%d\n",bulid(n));
}
return 0;
}
第二次:
为了减少循环次数,先对输入的所以权值从小到大排序, 依照循环次数每次取最小的两个, 合并成一个新的之后, 把新元素插入到该序列中,同时加到sum中, 这两个已经发挥出它的作用,所以不用在乎它是否被取代, 就这样,循环循环再循环
奇怪的是不管运行结果怎么正确我再如何修改,,都不能AC !!!!
下面第一个是我的,第二个是BF ' 对的...原理一样啊,别的没发现有什么不同
,,,,先放着吧...没心情看了
#include"stdio.h"//这是提交不对的!!!
#include"stdlib.h"
#include"algorithm"
#include"iostream"
using namespace std;
int huff[20010];
int cmp(const void*a,const void*b)
{
return *(int *)a - *(int *)b;
}
void build(int n)
{
long long money=0;
int min1,min2;//表示第1小,第2小
int sum,j;
int i;
qsort(huff,n,sizeof(int),cmp);//排序
i = 1;
int k;
for(k=1;k<n;k++)
{
sum = 0;
min1 = huff[i++];
min2 = huff[i++];
sum = min1 + min2;
money+= sum;
for(j=i;j<=n;j++)
if(huff[j]>sum) break;
else huff[j-1] = huff[j];
huff[j-1] = sum;
i--;
}
printf("%lld\n",money);
}
int main()
{
int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&huff[i]);//输入权值
if(n==1) printf("0\n");
else build(n);
}
return 0;
}
/*
1
234
4
1 1 1 1
0
6
1 2 3 4 5 6
*/
下面这个是AC的, 虽说有563ms,但是起码过了啊...
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int a[20002];
int cmp(const void * a,const void * b)
{
return *(int *)b - *(int *)a;
}
void Haffman(int num)
{
int n = num;
int i,j,k;
long long sum =0;
qsort(a,n,sizeof(int),cmp);
for(i=0;i<n-1;i++)
{
int temp = a[num-1]+a[num-2];
for(j=n-1;j>=0;j--)
{
if(temp<a[j]) break;
else a[j+1] = a[j];
}
a[j+1] = temp;
sum += temp;
num--;
}
printf("%lld\n",sum);
}
int main()
{
int i,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
if(n==1) printf("0\n");
else Haffman(n);
}
return 0;
}
当然还有第三种方法,简洁又快速的, 参照大牛的, 16ms
附代码:本大人加了详细滴注释~~~
#include<stdio.h>
#include<queue>
using namespace std;
priority_queue<int>hfmTree;//整形优先队列
void Init(__int64 &ans)//__int64和long long的范围相同
{ //ans代表花费
while(!hfmTree.empty()) //如果队列不同,就把队列中的元素全部出队
{ //也就是初始化队列
hfmTree.pop();
}
ans=0;
}
int main()
{
int N,in,tmp;//tmp存放的是较小的两个权值的和
__int64 ans;
while(scanf("%d",&N)!=EOF)
{
Init(ans); //由子函数知此时ans=0
while(N--) //输入权值并入队
{
scanf("%d",&in); //入队的时候带上负号就使得较小的就变成较大的值,即优先级最高
hfmTree.push(-in); //与一般队列不同,优先队列出队的总是优先级最高的
//这是便于出队时出来的是权值最小的~
}
while(!hfmTree.empty()) //如果优先队列非空,依次出队元素
{
tmp=hfmTree.top(),hfmTree.pop();//依次出队两个优先级最高的
if(!hfmTree.empty())
{
tmp+=hfmTree.top(),hfmTree.pop();
}
else //如果上一次出队之后队列为空,即上一个为最后一个元素
{ break; } //说明最后一切已经把木板切成最后的两部分了,循环结束
hfmTree.push(tmp);
ans+=tmp; //将新得到的两个最小值加起来的数入队参与下一次出队,并加到ans总和中
}
printf("%I64d\n",-ans); //加负号是把之前的负号去掉,负负得正嘛
}
return 0;
}
所以~知道的工具越多,解题越方便,AC越随意,也就越利于我们的高品质生活~O(∩_∩)O哈哈~,