企业官网建设流程全解析

题目描述

一艘船最多有999个货柜（编号为111到999），每个货柜有特定的最大承重能力（不超过999999999吨）。每个包裹重量不超过999吨，船上最多装载999999999个包裹。包裹通过传送带依次到达，由货物路由器按照以下算法分配到货柜：

规则1\texttt{1}1. 首先，只选择装载包裹数量最少的货柜。

规则2\texttt{2}2. 然后，在选出的货柜中，只选择可用承重能力最大的货柜。

规则3\texttt{3}3. 进一步筛选，选择编号最小的货柜。

规则4\texttt{4}4. 如果选中的货柜无法承载该包裹，则装船过程结束。

要求模拟该装载过程，输出每个货柜的最终内容、已装载包裹总重量、剩余可用重量以及未装载包裹总重量。

输入格式

输入包含多个测试用例，用例之间用空行分隔。每个测试用例首先给出货柜数量ccc（1≤c≤91 \le c \le 91≤c≤9），随后ccc行给出每个货柜的最大承重cwicwicwi（1≤cwi≤9991 \le cwi \le 9991≤cwi≤999）。接着是一个空行，然后给出包裹数量ppp（1≤p≤9991 \le p \le 9991≤p≤999），随后ppp行给出每个包裹的重量pwipwipwi（1≤pwi≤91 \le pwi \le 91≤pwi≤9）。保证所有包裹总重量不超过所有货柜总承重。

输出格式

对于每个测试用例，输出货柜的最终内容（按从顶部到底部的顺序，每行对应所有货柜在同一层的内容，空位用:表示），随后是一个空行，然后是已装载包裹总重量、剩余可用重量和未装载包裹总重量。相邻测试用例之间输出一个空行。

样例输入

3 5 10 5 8 4 3 2 1 1 2 3 4

样例输出

:3: 2 1 1 3 4 2 ===== 1 2 3 cargo weight: 16 unused weight: 4 unloaded weight: 4

题目分析

本题要求模拟一个按特定规则分配包裹的装载过程。核心在于准确实现四条选择规则，并正确处理装载终止条件。货柜数量最多为999，包裹数量最多为999999999，因此直接模拟即可，无需复杂优化。

规则1\texttt{1}1要求选择装载包裹数量最少的货柜。规则2\texttt{2}2在规则1\texttt{1}1的基础上选择可用承重最大的货柜。规则3\texttt{3}3在规则2\texttt{2}2的基础上选择编号最小的货柜。规则4\texttt{4}4检查选中的货柜是否能承载当前包裹：若能，则装入并更新货柜状态；若不能，则装载过程立即终止，后续所有包裹均视为未装载。

输出格式较为特殊：需要将每个货柜的内容按从顶部到底部的顺序逐层打印，每层对应所有货柜在该层的内容，若某货柜在该层没有包裹则输出:。分隔线由2c−12c - 12c−1个等号组成，货柜编号行由111到ccc组成。

解题思路

使用二维向量cargo存储每个货柜已装载的包裹重量，其中cargo[i]表示第iii个货柜的包裹列表，按装入顺序排列。使用数组capacity记录每个货柜的剩余可用承重，初始值为最大承重。使用布尔变量working标记装载过程是否仍在进行。

对于每个包裹，若working为真，则遍历所有货柜，按照规则1\texttt{1}1到规则3\texttt{3}3选出最佳货柜。具体比较逻辑为：优先比较包裹数量（越少越优）；若数量相同，比较剩余承重（越大越优）；若仍相同，比较编号（越小越优）。选出最佳货柜后，检查其剩余承重是否大于等于当前包裹重量：若是，则装入包裹，更新剩余承重和已装载总重量；若否，则将当前包裹计入未装载重量，并将working置为假。若working已为假，则直接将包裹计入未装载重量。

所有包裹处理完毕后，计算每个货柜的最大包裹数量maxPackage，然后从最高层到最低层逐层输出。对于每一层，遍历所有货柜，若该货柜在该层有包裹则输出包裹重量，否则输出:。层间用空格分隔。之后输出分隔线、货柜编号行、空行以及三个统计量。

时间复杂度为O(p×c)O(p \times c)O(p×c)，空间复杂度为O(p+c)O(p + c)O(p+c)，对于题目规模完全可行。

代码实现

// Loading a Cargo Ship// UVa ID: 945// Verdict: Accepted// Submission Date: 2017-03-14// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0,container;while(cin>>container){vector<vector<int>>cargo(container);vector<int>capacity(container);vector<int>usedWeight(container,0);inttotalCapacity=0;for(inti=0;i<container;i++){cin>>capacity[i];totalCapacity+=capacity[i];}intpackage,weight;inttotalWeight=0,cargoWeight=0,unusedWeight=0,unloadedWeight=0;boolworking=true;cin>>package;for(inti=0;i<package;i++){cin>>weight;totalWeight+=weight;if(working){intbest=0;for(intj=1;j<container;j++){if(cargo[j].size()<cargo[best].size())best=j;else{if(cargo[j].size()==cargo[best].size())if(capacity[j]>capacity[best])best=j;}}if(capacity[best]>=weight){cargo[best].push_back(weight);capacity[best]-=weight;cargoWeight+=weight;}else{unloadedWeight+=weight;working=false;}}elseunloadedWeight+=weight;}if(cases++>0)cout<<'\n';intmaxPackage=0;for(inti=0;i<container;i++)maxPackage=max(maxPackage,(int)cargo[i].size());for(inti=maxPackage-1;i>=0;i--){for(intj=0;j<container;j++){if(j>0)cout<<' ';if(i<cargo[j].size())cout<<cargo[j][i];elsecout<<':';}cout<<'\n';}for(inti=1;i<=(2*container-1);i++)cout<<'=';cout<<'\n';for(inti=1;i<=container;i++){if(i>1)cout<<' ';cout<<i;}cout<<'\n';cout<<'\n';cout<<"cargo weight: "<<cargoWeight<<'\n';cout<<"unused weight: "<<(totalCapacity-cargoWeight)<<'\n';cout<<"unloaded weight: "<<unloadedWeight<<'\n';}return0;}

总结

本题的关键在于准确实现货柜选择的优先级规则，并注意装载终止后所有后续包裹均计入未装载重量。输出格式较为繁琐，需要按层打印货柜内容，空位用:表示，并注意分隔线与编号行的对齐。时间复杂度为O(p×c)O(p \times c)O(p×c)，空间复杂度为O(p+c)O(p + c)O(p+c)，能够高效处理题目规模的数据。