Desirer's blog

集装箱堆叠

https://mp.weixin.qq.com/s/RJpeftXV4Ikza-ApvAQfIQ

题目内容

描述:某码头有一批集装箱,每个集装箱形状大小一致。

由于材质不同，每个集装箱上方可堆叠的集装箱个数不同。 如: 标号的集装箱，则不可在其上方放置集装箱;

标号1的集装箱，其上方最多可放置1个集装箱;

标号n的集装箱，其上方最多可放置n个集装箱;

给定一批集装箱，假设每个集装箱底面积为1，求如何堆叠使得占地面积最小，并输出最小面积。

输入描述

输入为一行整形数组的字符串，每个数字以空格隔开

输出描述

值，最小面积。

示例

输入

0 2 1

输出

1

最少可堆叠为1垛，堆叠顺序自下而上依次为:2标号集装箱、1标号集装箱、0标号集装箱。

输入

1 2 1 2

输出

2

思路

这题有点像汉诺塔问题，大集装箱必须放在小集装箱下面。问题是怎么样使得占地面积最小。

很容易想到排序，因为我们需要某种顺序进行堆叠。如果是降序，我们不能确定大集装箱的占地面积（因为它们之间可以堆叠）。相反，如果是升序，我们可以确定这样一个性质：占地面积最少为标号0的集装箱个数。

于是确定这样一种算法：

1. 将集装箱安装大小升序排序，保存在v中

2. 建立一个multiset用来维护跺堆的高度

3. 遍历v，每次取出一个集装箱box

   1. 遍历multiset，找到小于box高度的跺堆

   2. 将这个box更新到这个跺堆中（跺堆高度+1，然后更新multiset）

      其实就是将这个box塞到能塞的最高高度的跺堆中

4. 最后的占地面积就是mutliset的size

代码

int main() {
    vector<int> nums;
    int tmp;
    while(cin>>tmp){
        nums.push_back(tmp);
        if(getchar()=='\n') break;
    }

    sort(nums.begin(), nums.end());
    multiset<int> mset;
    for(auto num : nums){
       // 1、 find height<=num in mset
        /*返回指向首个不小于给定键的元素的迭代器 */
        auto it = mset.lower_bound(num);
       // 2、 if none，原地放置箱子
       if(it==mset.begin() && *it>num){
           mset.insert(1);
           continue;
       }
       // 3、 else 将其放置在那列箱子下面
       int height_below_num = -1;
       if(it!=mset.begin() && *it>num)
            height_below_num = *(--it);
       else
           height_below_num = *it;
       mset.erase(it);
       mset.insert(height_below_num+1);
    }
    cout<<mset.size();
}