题解：The Trip, 2007（旅行行李嵌套问题）

一、题目分析

本题要求将多个尺寸不同的袋子进行嵌套打包，使得：

1. 行李件数最少：即最外层袋子的数量最少，等价于每种尺寸的袋子中，出现次数最多的尺寸的出现次数（因为每个行李件只能包含一个该尺寸的袋子作为最外层）。
2. 在行李件数最少的前提下，单个行李件中的袋子数量尽可能少：通过合理分配各尺寸袋子到不同的行李件中，使得每个行李件的袋子数量均匀分布。

二、核心思路

1. 确定最少行李件数：
   最少行李件数由出现次数最多的尺寸的袋子数量决定。例如，若某尺寸袋子出现了 ( u ) 次，则至少需要 ( u ) 个行李件（每个行李件的最外层只能是一个该尺寸的袋子）。

2. 分配袋子到行李件：

   • 首先对所有袋子的尺寸进行排序。
   • 将排序后的袋子按行李件数 ( u ) 进行分组，每个行李件依次取第 ( i, i+u, i+2u, \dots ) 个袋子（( i ) 为行李件编号，从 0 到 ( u-1 )）。这样可以确保每个行李件内的袋子尺寸递增（因为排序后尺寸非递减），且每个行李件的袋子数量尽可能均衡，从而满足“单个行李件中的袋子数量最少”的要求。

三、代码解析

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 1000100  // 最大尺寸值+1

int c[N];  // 统计各尺寸的出现次数
int a[N];  // 存储所有袋子尺寸

int main() {
    int n;
    while (scanf("%d", &n) != EOF && n != 0) {
        memset(c, 0, sizeof(c));  // 初始化计数数组
        int max_count = 0;        // 记录最大出现次数（即最少行李件数）
        
        // 读取所有袋子尺寸并统计出现次数
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            c[a[i]]++;
            if (c[a[i]] > max_count) {
                max_count = c[a[i]];  // 更新最大出现次数
            }
        }
        
        // 对袋子尺寸进行排序（非递减顺序）
        sort(a, a + n);
        
        // 输出最少行李件数
        printf("%d\n", max_count);
        
        // 分配袋子到各个行李件中
        for (int i = 0; i < max_count; i++) {
            // 每个行李件的第一个元素为 a[i]
            printf("%d", a[i]);
            // 依次取间隔为 max_count 的元素，填充当前行李件
            for (int j = i + max_count; j < n; j += max_count) {
                printf(" %d", a[j]);
            }
            printf("\n");
        }
        
        // 测试用例之间输出空行（题目要求）
        static bool first_case = true;
        if (!first_case) {
            printf("\n");
        }
        first_case = false;
    }
    return 0;
}

四、步骤详解

1. 输入处理与统计：

   • 使用数组 c 统计每个尺寸的出现次数，同时记录最大出现次数 max_count，该值即为最少行李件数。

2. 排序：

   • 对袋子尺寸进行排序，确保后续分配时每个行李件内的尺寸递增（满足嵌套条件）。

3. 分配袋子到行李件：

   • 每个行李件从索引 i 开始（i 从 0 到 max_count-1），依次取索引为 i, i+max_count, i+2*max_count, ... 的袋子。
   • 例如，当 max_count=3，n=6 时，第一个行李件取 a[0], a[3]，第二个取 a[1], a[4]，第三个取 a[2], a[5]，确保每个行李件内的尺寸递增且数量均衡。

4. 输出格式处理：

   • 每个测试用例之间需输出空行，通过静态变量 first_case 控制。

五、关键点总结

• 最少行李件数的确定：由出现次数最多的尺寸决定，这是问题的核心约束。
• 贪心分配策略：排序后按间隔分配，确保每个行李件内的尺寸递增，且数量均衡，从而满足“单个行李件数量最少”的要求。
• 复杂度分析：排序的时间复杂度为 ( O(n \log n) )，适用于 ( n \leq 10000 ) 的数据规模。

该解法通过简单的统计和排序，高效地解决了嵌套打包问题，确保了最优解的两个条件同时满足。