topcoder SRM 622 DIV2 BoxesDiv2

注意题目这句话,Once you have each type of candies in a box, you want to pack those boxes into larger boxes, until only one box remains.

两个box合并后必须放入更大一个盒子

题目的有点类似huffman的前部分,此题用堆去做,由于priority_queue是用堆实现的,故可以直接使用

每次从堆中选取最小的两个进行合并即可

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std; class BoxesDiv2{
public:
int round_up(int x){
for(int i = ; i <= ; ++ i){
if( <<i >= x ) return <<i;
}
return <<;
} int findSize(vector<int> candyCounts){
priority_queue<int,vector<int>,greater<int> > boxQueue;
for(int i = ; i < candyCounts.size(); ++ i){
boxQueue.push(round_up(candyCounts[i]));
}
while(boxQueue.size() != ){
int a = boxQueue.top();boxQueue.pop();
int b = boxQueue.top();boxQueue.pop();
boxQueue.push(max(a,b)*);
}
return boxQueue.top();
}
};
上一篇:【转】SignalR来做实时Web聊天


下一篇:Java Web程序设计笔记 • 【第3章 JSP内置对象】