当前位置:首页 > 图灵资讯 > 技术篇> poj-3253

poj-3253

发布时间:2023-05-24 09:25:32

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也经常使用队列来解决一些算法问题.

上一篇 poj-2503
下一篇 poj-2251

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题