Poj3253：Fence Repair 【贪心堆】

题目大意：背景大概是个资本家剥削工人剩余价值的故事。。。。有一块木板，要把它切成几个长度，切一次的费用是这整块被切木板的长度，例如将一个长度为21的木板切成2和19两块费用为21，切成两块的长度及顺序是可以自己定的，问最小费用是多少

思路：一个很明显的贪心思路是每次将最长切下来，这样后续切割就不会用到这根最长的木板，结果也就是最优的了。具体操作的时候可以倒过来想：有一系列切完的小木板，要将它们合并成一块大木板，费用为合并完后那个大木板的长度，问最小费用。这样，每次合并最小木板的思路就跃然纸上了-----每次将小木板中最小的两块木板合并，更新答案，将合并后的木板加到原来的木板中，由于每次要更新最小值，因此采取堆优化应该是不错的方式。

#include<cstdio>

#include<string.h>

#include<iostream>

using namespace std;

int heap[50009]={0},last=1;

void swap(int i,int j)

{

int temp=heap[i];heap[i]=heap[j];heap[j]=temp;

}

void add(int value)

{

int i=last;

heap[last++]=value;

while(heap[i]<heap[i>>1]&& i>1)

{

swap(i,i>>1);

i=i>>1;

}

void del()

{

heap[1]=heap[--last];

heap[last]=0;

int i=1,next;

next=heap[(i<<1)]<heap[(i<<1)+1]?i<<1:(i<<1)+1;

if ((i<<1)+1>=last)next=i<<1;

while(heap[i]>heap[next] && next<last)

{

swap(i,next);

i=next;

if ((i<<1)+1>=last)next=i<<1;elsenext=heap[(i<<1)]<heap[(i<<1)+1]? i<<1:(i<<1)+1;

}

int main()

{

int n,t;

__int64 ans=0;

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&t);add(t);

}

for(int i=1;i<=n-1;i++)

{

int top=heap[1];del();

top+=heap[1];ans+=top;

del();add(top);

}

printf("%I64d\n",ans);

return 0;

}

调试结果：1WA 原因：heap写错了贡献了一次wa

自测数据：input：

56 123 7 123 41 4 1 33 54 78 64

Output：

1462

巴特西

Poj3253：Fence Repair 【贪心堆】

最新文章

热门文章

巴特西

Poj3253：Fence Repair 【贪心 堆】

最新文章

热门文章

Poj3253：Fence Repair 【贪心堆】