题目描述
题目要求模拟将一列包装箱（每组包含111到444个单元箱）堆放到一个666英尺长、202020英尺高的货箱中。货箱宽度为111英尺，每个单元箱是1×1×11 \times 1 \times 11×1×1英尺的立方体。包装箱必须完整放置，不能拆分。放置时，包装箱可以水平放置（占据连续多个位置）或垂直放置（在同一个位置上堆叠）。水平放置时，包装箱必须被其下方的整个长度完全支撑（即下方所有对应位置的高度必须相同）。目标是按输入顺序尽可能多地放置包装箱，并输出成功放置的包装箱数量以及最终剩余的空位数量（总容量为6×20=1206 \times 20 = 1206×20=120个单元箱）。
输入格式
输入包含若干行，每行一个由数字111、222、333、444组成的字符串，表示包装箱的大小序列。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每行输入，输出一行两个整数：成功放置的包装箱数量和剩余的空位数量。
样例
输入
4444444444444444444444444444444444444444444444444444444444444 3333333333333333333333333333333333333333333333333333333333333输出
30 0 39 3题目分析
本题的核心是贪心模拟堆叠过程。每次处理一个包装箱时，优先尝试水平放置，若不能则尝试垂直放置，若两者均不能则停止。
状态表示
使用数组bin[6]\textit{bin}[6]bin[6]表示每个位置当前的高度（已放置的单元箱层数），初始全为000。每个位置最大高度为202020。
水平放置
对于大小为ppp的包装箱，尝试在000到6−p6-p6−p之间寻找起始位置jjj，使得：
- bin[j]\textit{bin}[j]bin[j]到bin[j+p−1]\textit{bin}[j+p-1]bin[j+p−1]的高度相同（保证支撑面平整）。
- 该高度小于202020（因为放置后不能超过202020）。
若找到，则将bin[j]\textit{bin}[j]bin[j]到bin[j+p−1]\textit{bin}[j+p-1]bin[j+p−1]各加111，表示放置成功。
垂直放置
若水平放置失败，则尝试在任意位置jjj上垂直堆叠（即包装箱竖着放，占据该位置的ppp个单元箱）。要求bin[j]+p≤20\textit{bin}[j] + p \le 20bin[j]+p≤20。选择第一个满足条件的位置放置，并将bin[j]\textit{bin}[j]bin[j]增加ppp。
终止条件
若水平放置和垂直放置均失败，则后续包装箱均无法放置，停止处理。
输出
成功放置的包装箱数量即为处理到的位置数（从000开始计数）。剩余空位数 =120120120- 已放置的单元箱总数。
贪心策略的合理性
优先尝试水平放置可以保持高度均匀，为后续包装箱创造更多的水平放置机会。垂直放置是后备方案。该贪心策略在本题中可得到最优解。
复杂度分析
每个包装箱最多检查O(6×p)O(6 \times p)O(6×p)个位置，p≤4p \le 4p≤4，总复杂度O(包装箱数×24)O(\text{包装箱数} \times 24)O(包装箱数×24)，完全可接受。
代码实现
// Robotic Stacker// UVa ID: 456// Verdict: Accepted// Submission Date: 2017-02-25// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metapackageshysis # yeah dot net//// greedy algorithm works, why?//#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string s;while(cin>>s){intbin[6]={},stacked=0,boxes=0;for(inti=0;i<s.length();i++,stacked++){intpackages=s[i]-'0';// 尝试将箱子水平放置在集装箱内。boolhorizontal=false;for(intj=0;j<=6-packages;j++){if(bin[j]!=20){boolsupported=true;for(intk=1;k<packages;k++)if(bin[j+k]!=bin[j]){supported=false;break;}if(supported){for(intk=0;k<packages;k++)bin[j+k]++;horizontal=true;break;}}}// 水平放置成功。if(horizontal){boxes+=packages;continue;}// 若水平放置不成功，尝试垂直放置。boolvertical=false;for(intj=0;j<6;j++){if(bin[j]+packages<=20){bin[j]+=packages;vertical=true;break;}}// 若垂直放置不成功，表明该组箱子无法放置。if(!vertical)break;boxes+=packages;}cout<<stacked<<' '<<(120-boxes)<<'\n';}return0;}
