[各种面试题] 堆放积木

有n块积木，每块积木有体积vol和重量weight两个属性，用二元组(vol, weight)表示。积木需要搭成竖直的塔状，上面积木的体积和重量必须都比它下面的积木小。问最多可以搭多少个积木。

样例：

有7个积木boxes:
[(65, 100), (70, 150), (56, 90), (75, 190), (60, 95), (68, 110), (80, 12)]
最多可以搭6个积木，从上到下分别为：
(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)
所以函数应该返回6。

题目来源：CRACKING THE CODING INTERVIEW 9.7

其实就是个最长递减子序列的题，先排序，朴素的办法是O(n2)的，如果是一维的话可以用二分查找优化为O(nlong)，但是二维的貌似这个优化行不通。

/*积木的定义(请不要在代码中定义该结构)
struct Box {
int vol, weight;
};*/
struct compare
{
bool operator()(const Box& b1,const Box& b2)const
{
if (b1.vol==b2.vol)
return b1.weight>b2.weight;
return b1.vol>b2.vol;
}
};
int maxBoxes(vector<Box> &boxes) {
if (boxes.empty())
return 0;
sort(boxes.begin(),boxes.end(),compare());
vector<int> longest(boxes.size(),1);
for(int i=1;i<longest.size();i++)
{
int t=1;
for(int k=i-1;k>=0;k--)
{
if ( boxes[k].vol >boxes[i].vol &&
boxes[k].weight>boxes[i].weight )
t=max(t,longest[k]+1);
}
longest[i]=t;
}
return *max_element(longest.begin(),longest.end());
}

最后

以上就是怕黑红牛为你收集整理的[各种面试题] 堆放积木的全部内容，希望文章能够帮你解决[各种面试题] 堆放积木所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。