Greedy:Fence Repair（POJ 3252）

　　　　　　　　　　　　　　　Fence Repair

　　问题大意：农夫约翰为了修理栅栏，要将一块很长的木块切割成N块，准备切成的木板的长度为L1，L2...LN，未切割前的木板的长度恰好为切割后木板的长度的总和，每次切断木板的时候，需要的开销为这块木板的长度，例如长度为21的木板需要切成长度为5,8,8的三块木板，长为21的木板切成长为13和8的板时，开销为21,。再将长度为13的板切成长度为5和8的板时，开销是13，于是合计开销是34，然后要你求切割完的最小开销是什么。

　　乍眼看这一道题好像有很多种切割方案，似乎是很难解决的，但是我们这样想，就是当我们切一块木板的时候，我们所用的开销就是切割这一块木板所要用到的长度，我们得到了两块木板，这两块木板可以继续切的话，他们的总开销就是这两块木板的和，也就是一块长的木板。那么我们想到最后，就会发现其实就是我们得到了一个这样的东西，就是最小的板会所要用到的开销会占N次（视通过多少次分割得到这块板来定），如果我们要画一幅图来展示这个过程的话。。。

　　上面最大的开销是34=8*2+5*2+8（也就是二叉树的树叶对应节点大小乘以高度）

　　那么为了得到最小的开销，我们很容易就发现，我们只要把相对较小的节点放在比较深的地方就可以了，这是一种比较常用的贪婪的思想，证明我就省略了

那么现在我们只用不断地把最小的节点结合起来，最后就会形成最小的开销，那么不断找最小嘛，很容易就想到用堆，堆呢你可以自己写（熟练的话会很快），也可以直接用std（会比较简洁）

 #include<stdio.h>

 #include<stdlib.h>

 typedef int Position, *Heap;

 int Delete_Min(Heap, int *const);

 void Push(Heap, int, int *const);

 int main(void)

 {

     int N, i, size = ;

     int L1, L2, tmp;

     long long ans = ;

     while (~scanf("%d",&N))

     {

         Heap pque = (Heap)malloc(sizeof(int)*N);

         for (i = ; i < N; i++)

         {

             scanf("%d", &tmp);

             Push(pque, tmp, &size);

         }

         while (size > )

         {

             L1 = Delete_Min(pque, &size);

             L2 = Delete_Min(pque, &size);

             ans += (long long)L1 + L2;

             Push(pque, L1 + L2, &size);

         }

         free(pque);

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

     }

 }

 int Delete_Min(Heap heap,int *const size)

 {

     Position pr = , s1, s2, s;

     int out = heap[], tmp = heap[(*size)--];

     for (; pr <= *size;)

     {

         s1 = pr << ; s2 = s1 + ;

         if (s2 <= *size)

         {

             if (heap[s1] < heap[s2]){ heap[pr] = heap[s1]; pr = s1; }

             else{ heap[pr] = heap[s2]; pr = s2; }

         }

         else

         {

             if (s1 <= *size){ heap[pr] = heap[s1]; pr = s1;break; }

             else break;

         }

     }

     for (s = pr; s > ;)

     {

         if (s %  == )

         {

             pr = s >> ;

             if (heap[pr] > tmp) { heap[s] = heap[pr];s = pr;}

             else break;

         }

         else

         {

             pr = (s - ) >> ;

             if (heap[pr] > tmp){ heap[s] = heap[pr];s = pr; }

             else break;

         }

     }

     heap[s] = tmp;

     return out;

 }

 void Push(Heap heap, int item, int *const size)

 {

     Position s = ++(*size), pr;

     for (; s > ;)

     {

         if (s %  == )

         {

             pr = s >> ;

             if (heap[pr] > item) { heap[s] = heap[pr]; s = pr; }

             else break;

         }

         else

         {

             pr = (s - ) >> ;

             if (heap[pr] > item){ heap[s] = heap[pr]; s = pr; }

             else break;

         }

     }

     heap[s] = item;

 }

这是直接写堆的代码

 #include<iostream>

 #include<queue>

 #include<functional>

 #include<cstdio>

 using namespace std;

 int main(void)

 {

     int N, i;

     int L1, L2, tmp;

     long long ans = ;

     while (~scanf("%d", &N))

     {

         priority_queue<int, vector<int>, greater<int> >pque;

         for (i = ; i < N; i++)

         {

             scanf("%d", &tmp);

             pque.push(tmp);

         }

         while (pque.size() > )

         {

             L1 = pque.top();

             pque.pop();

             L2 = pque.top();

             pque.pop();

             ans += (long long)L1 + L2;

             pque.push(L1 + L2);

         };

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

     }

 }

这是用的std，事实上呢用std是挺方便的，虽然稍微损失了一下性能，我直接用堆是472K,32ms，用std是920k,47ms，相差不大

另外这个思想还可以用来做著名的Huffman编码，其实Huffman以前写了一个，以后会贴出来看看

巴特西

Greedy:Fence Repair（POJ 3252）

最新文章

热门文章