poj-3253

C++ 94ms(STL queue)

#include <iostream>  #include <queue>  #include <vector>  #include <cstring>  using namespace std;  priority_queue<long long, vector<long long>, greater<long long> > intQueue;  const int QUEUE_SIZE = 20010;  template <typename T>  struct LessComparator {      char operator()(const T & p1, const T & p2) {          return p1 < p2;      }  };     template <typename T, class C>  class my_priroity_queue {  private:      T mArray[QUEUE_SIZE];      int mQueueSize;      C mComparator;      void adjust_heap_node_up(int NodePos) {          int parentPos = NodePos;          int leftChildPos = 2*NodePos + 1;          int rightChildPos = 2*NodePos + 2;          // cout<<"p "<<parentPos<<" l "<<leftChildPos<<" r "<<rightChildPos<<" "<<mArray[leftChildPos]<<" "<<mArray[parentPos]<<" "<<mArray[rightChildPos]<<endl;          if (rightChildPos + 1 <= mQueueSize) {  // 2              int min = mComparator(mArray[parentPos], mArray[leftChildPos]) ? parentPos : leftChildPos;              min =  mComparator(mArray[min], mArray[rightChildPos]) ? min : rightChildPos;              if (min == parentPos) {                  // cout<<"2 == "<<parentPos<<" "<<mArray[leftChildPos]<<" "<<mArray[parentPos]<<" "<<mArray[rightChildPos]<<endl;                  return;              } else {                  T tmp = mArray[min];                  mArray[min] = mArray[parentPos];                  mArray[parentPos] = tmp;                  if (!parentPos) {                      return;                  }                  adjust_heap_node_up((parentPos-1)/2);              }          } else if (leftChildPos + 1 <= mQueueSize){  // 1              int min = mComparator(mArray[parentPos], mArray[leftChildPos]) ? parentPos : leftChildPos;              if (min == parentPos) {                  // cout<<"1 == "<<parentPos<<endl;                  return;              } else {                  T tmp = mArray[min];                  mArray[min] = mArray[parentPos];                  mArray[parentPos] = tmp;                  if (!parentPos) {                      return;                  }                  adjust_heap_node_up((parentPos-1)/2);                 }          } else {              // cout<<"3 return "<<NodePos<<endl;              return;          }          }      void adjust_heap_node_down(int NodePos) {          int parentPos = NodePos;          int leftChildPos = 2*NodePos + 1;          int rightChildPos = 2*NodePos + 2;          if (rightChildPos + 1 <= mQueueSize) {  // 2              int min = mComparator(mArray[parentPos], mArray[leftChildPos]) ? parentPos : leftChildPos;              min =  mComparator(mArray[min], mArray[rightChildPos]) ? min : rightChildPos;              if (min == parentPos) {                  return;              } else {                  T tmp = mArray[min];                  mArray[min] = mArray[parentPos];                  mArray[parentPos] = tmp;                  if (min*2 + 2 + 1 > mQueueSize) {                      return;                  }                  adjust_heap_node_down(min);              }          } else if (leftChildPos + 1 <= mQueueSize){  // 1              int min = mComparator(mArray[parentPos], mArray[leftChildPos]) ? parentPos : leftChildPos;              if (min == parentPos) {                  return;              } else {                  T tmp = mArray[min];                  mArray[min] = mArray[parentPos];                  mArray[parentPos] = tmp;                  if (min*2 + 1 + 1 > mQueueSize) {                      return;                  }                  adjust_heap_node_down(min);                 }          } else {              // cout<<"3 return "<<NodePos<<endl;              return;          }          }      void matain_heap_after_insert() {          int beginNode = (mQueueSize-2)/2;          adjust_heap_node_up(beginNode);      }      void matain_heap_after_pop() {          int beginNode = 0;          adjust_heap_node_down(beginNode);      }  public:      my_priroity_queue(C cmp):  mQueueSize(0), mComparator(cmp) {          memset(mArray, 0, sizeof(mArray));      }      T top() {          return mArray[0];      }      void push(T val) {          mArray[mQueueSize++] = val;          matain_heap_after_insert();          // cout<<"size "<<mQueueSize<<endl;          // for (int i = 0; i < mQueueSize; i++) {          //     cout<<mArray[i]<<endl;          // }      }      void pop() {          if (mQueueSize) {              mArray[0] = mArray[--mQueueSize];              if (mQueueSize) {                  matain_heap_after_pop();              }          }      }      int size() {          return mQueueSize;      }  };  struct LessComparator<long long> cmp;  my_priroity_queue<long long, struct LessComparator<long long> > my_queue(cmp);  void getMinCost() {      long long totalCost = 0;      while(my_queue.size() > 1) {          long long costThisTime = my_queue.top();          // cout<<my_queue.top()<<endl;          my_queue.pop();          costThisTime += my_queue.top();          // cout<<my_queue.top()<<endl;          my_queue.pop();          my_queue.push(costThisTime);          totalCost += costThisTime;      }      //totalCost += intQueue.top();      my_queue.pop();      cout<<totalCost<<endl;  }  int TEST() {      cout<<"TEST"<<endl;      my_queue.push(537);      my_queue.push(4189);      my_queue.push(652);      my_queue.push(3127);      // my_queue.pop();      // cout<<"RES"<<endl;      // while(my_queue.size()) {      //     cout<<my_queue.top()<<endl;      //     my_queue.pop();      // }      my_queue.push(4673);      my_queue.push(1364);      my_queue.push(40);      // my_queue.pop();      // cout<<"RES"<<endl;      // while(my_queue.size()) {      //     cout<<my_queue.top()<<endl;      //     my_queue.pop();      // }      my_queue.push(854);      my_queue.push(2326);      my_queue.push(1016);      my_queue.push(1307);      my_queue.push(3372);      my_queue.push(4663);      my_queue.push(2164);      my_queue.push(2833);      my_queue.push(3037);      my_queue.push(4758);      my_queue.push(4757);      my_queue.push(4633);      my_queue.push(2942);      cout<<"RES"<<endl;      my_queue.pop();      my_queue.pop();      my_queue.push(577);      while(my_queue.size()) {          cout<<my_queue.top()<<endl;          my_queue.pop();      }  }  int main() {      // TEST();      while(1) {          int num = 0;          cin>>num;          if (cin.eof()) {              return 0;          }          // intQueue.clear();          for (int i = 0; i < num; i++) {              long long tmp;              cin>>tmp;              my_queue.push(tmp);          }          getMinCost();          // while(intQueue.size()) {          //     cout<<intQueue.top()<<endl;          //     intQueue.pop();          // }      }  }

G++ 157MS(自己写的优先级queue)

使用哈夫曼树和STL的原理 priority_queue.

这个问题让我重新认识了哈夫曼树，以前对哈夫曼树的理解仅限于求编码的例子。

当我遇到这个问题时，我没想到会使用哈夫曼。起初，我想使用动态规划。后来，我发现虽然DP理论上可以使用，但基本上不可能与这个问题相结合，因为数字太多（2万）

后来，我看到有人说我可以用哈夫曼，但我不明白为什么我可以把它转化成哈夫曼树。后来，我仔细阅读了算导哈夫曼树：

对于一系列值Array来说，哈夫曼树可以获得这样的最小值[i]：

D(i)*Array(i)全部和最小。 其中 D(i)哈夫曼树中的深度是值(叶节点)，Array[i]是数组的第一个值。

所以对于这个问题，按照锯木的顺序建造一棵二叉树，那么总成本也可以表示为:

D(i)*L(i)的总和, D(i) 是树中第一个plank的深度，而L(i)是plank 为什么i的长度总成本可以用这种方式来表示，

因为对于一个plank来说，plank从开始切割到最后终于被切割了 因为plank，i被切掉了 Di带来的cost总共是Dost(i)*L(i),

举个简单的例子， 五个plank， L: 1 2 3 4 5

这种切割顺序：

12345

12 345

1 2 3 45

4 5

可以看出，切割4/5的总成本是其长度乘以其深度（这是因为除非plank被切割，否则它将不可避免地参与下一个分割，因此其长度将附加到下一个切割成本中）。

也可以称之为求树所有父节点和最小问题(因为每个父节点必须一次切割，成本是两个子节点的成本和)

这样，它就可以转化为哈夫曼树的问题。

记住这种经典的哈夫曼树应用模式。

还需要注意的是，最后的cost应该使用long long

写优先级queue时，在求父子节点index表示时，因为数组index是从0开始的，

因此，对于父节点indexx = p,inex子节点: left = 2*p + 1 right = 2*right + 2

对于子节点indexx = i, 父节点应该是(i-2)/2。

BFS也经常使用队列来解决一些算法问题.