题面描述

某码头有一批集装箱，每个集装箱形状大小一致。由于材质不同，每个集装箱上方可堆叠的集装箱个数不同。具体规则如下：

• 标号为 $0$ 的集装箱，不能在其上方放置任何集装箱；
• 标号为 $1$ 的集装箱，其上方最多可放置 $1$ 个集装箱；
• 标号为 $n$（$0 \leq n \leq 10^6$）的集装箱，其上方最多可放置 $n$ 个集装箱。

给定一批集装箱，假设每个集装箱的底面积为 $1$，要求通过合理堆叠使得占地面积（即堆垛的数量）最小，并输出最小的占地面积。

思路

将所有箱子按照升序排序，用一个多重集合来存储当前有的集装箱的高度，对于每一个集装箱记为$c$，找到当前满足$<=c$的最大高度，如果没有就新建一个，如果有就将它的高度更新为$c+1$

具体思路如下：

1. 排序：首先将所有集装箱按照其标号进行非降序排序。这有助于优先处理标号较小的集装箱，使得它们能够更灵活地堆叠在已有的堆垛上。

2. 堆垛管理：使用一个多重集合（multiset）来维护当前所有堆垛的高度。对于每一个集装箱，尝试将其放置在一个已经存在的堆垛上，要求该堆垛的当前高度不超过该集装箱的标号（即可以在堆垛的下方加一个新的）。

   • 查找适合的堆垛：对于当前集装箱，寻找一个堆垛，其高度是小于或等于该集装箱标号的最大值。这可以通过在 multiset 中查找不大于当前标号的最大值来实现。

   • 更新堆垛高度：如果找到这样的堆垛，则将该堆垛的高度加一（因为新集装箱被放置在其上）；否则，新建一个堆垛，其高度初始化为 1。

3. 结果：最终，多重集合中堆垛的数量即为最小的占地面积。

该方法的时间复杂度主要受排序和每次插入、删除操作的影响，整体为 $O(n \log n)$，适用于题目给定的规模。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    // 读取整行输入
    string s;
    getline(cin, s);
    // 分割字符串为整数
    vector<int> containers;
    int num;
    stringstream ss(s);
    while(ss >> num){
        containers.push_back(num);
    }
    // 按非降序排序
    sort(containers.begin(), containers.end());
    cout<<endl;
    // 使用multiset维护堆垛的当前高度
    multiset<int> stacks;
    for(auto& c : containers){
        // 查找最大的堆垛高度 <= c
        // upper_bound返回第一个 >c 的迭代器
        auto it = stacks.upper_bound(c);
        if(it == stacks.begin()){
            // 没有堆垛可以放置，创建新堆垛
            stacks.insert(1);
        }
        else{
            // 有堆垛可以放置，选择最大的堆垛
            --it;
            
            int new_height = *it +1;
            stacks.erase(it);
            stacks.insert(new_height);
        }
    }
    // 输出堆垛数量
    cout << stacks.size();
}

python

def main():
    # 读取整行输入
    s = input()
    # 分割字符串为整数
    containers = list(map(int, s.split()))
    # 按非降序排序
    containers.sort()


    # 使用多重集合维护堆垛的当前高度
    stacks = []

    for c in containers:
        # 查找最大的堆垛高度 <= c
        valid_stacks = [height for height in stacks if height <= c]

        if not valid_stacks:
            # 没有堆垛可以放置，创建新堆垛
            stacks.append(1)
        else:
            # 有堆垛可以放置，选择最大的堆垛
            max_height = max(valid_stacks)
            stacks.remove(max_height)

            new_height = max_height + 1
            stacks.append(new_height)

    # 输出堆垛数量
    print(len(stacks))


if __name__ == "__main__":
    main()

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建输入扫描器
        Scanner scanner = new Scanner(System.in);
        
        // 读取整行输入
        String s = scanner.nextLine();
        
        // 将输入字符串分割并转换为整数数组
        int[] containers = Arrays.stream(s.split(" "))
                                  .mapToInt(Integer::parseInt)
                                  .toArray();
        
        // 按非降序排序
        Arrays.sort(containers);

        // 使用列表维护堆垛的当前高度
        List<Integer> stacks = new ArrayList<>();

        for (int c : containers) {
            // 查找最大的堆垛高度 <= c
            List<Integer> validStacks = new ArrayList<>();
            for (int height : stacks) {
                if (height <= c) {
                    validStacks.add(height);
                }
            }

            if (validStacks.isEmpty()) {
                // 没有堆垛可以放置，创建新堆垛
                stacks.add(1);
            } else {
                // 有堆垛可以放置，选择最大的堆垛
                int maxHeight = validStacks.stream().mapToInt(Integer::intValue).max().orElse(0);
                stacks.remove(Integer.valueOf(maxHeight));

                int newHeight = maxHeight + 1;
                stacks.add(newHeight);
            }
        }

        // 输出堆垛数量
        System.out.println(stacks.size());

        // 关闭扫描器
        scanner.close();
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int [] a = Arrays.stream(inputs).mapToInt(Integer::parseInt).toArray();
        Arrays.sort(a);
        // 考虑在每一步选择
        ArrayList<Integer> heightList = new ArrayList<>();
        for (int i = 0; i < a.length; i ++ ) {
            // height 数组是有序的，二分查找可以添加箱子的位置
            if (heightList.isEmpty()) {
                heightList.add(1);
                continue;
            }
            int l = 0, r = heightList.size() - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (heightList.get(mid) > a[i]) l = mid + 1;
                else r = mid;
            }
            if (heightList.get(l) <= a[i]) {
                heightList.set(l, heightList.get(l) + 1);
            }else {
                heightList.add(1);
            }
        }
        System.out.println(heightList.size());
    }
}