UVa 945 Loading a Cargo Ship

题目描述一艘船最多有999个货柜编号为111到999每个货柜有特定的最大承重能力不超过999999999吨。每个包裹重量不超过999吨船上最多装载999999999个包裹。包裹通过传送带依次到达由货物路由器按照以下算法分配到货柜规则1\texttt{1}1. 首先只选择装载包裹数量最少的货柜。规则2\texttt{2}2. 然后在选出的货柜中只选择可用承重能力最大的货柜。规则3\texttt{3}3. 进一步筛选选择编号最小的货柜。规则4\texttt{4}4. 如果选中的货柜无法承载该包裹则装船过程结束。要求模拟该装载过程输出每个货柜的最终内容、已装载包裹总重量、剩余可用重量以及未装载包裹总重量。输入格式输入包含多个测试用例用例之间用空行分隔。每个测试用例首先给出货柜数量ccc1≤c≤91 \le c \le 91≤c≤9随后ccc行给出每个货柜的最大承重cwicwicwi1≤cwi≤9991 \le cwi \le 9991≤cwi≤999。接着是一个空行然后给出包裹数量ppp1≤p≤9991 \le p \le 9991≤p≤999随后ppp行给出每个包裹的重量pwipwipwi1≤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(pc)O(p c)O(pc)对于题目规模完全可行。代码实现// Loading a Cargo Ship// UVa ID: 945// Verdict: Accepted// Submission Date: 2017-03-14// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0,container;while(cincontainer){vectorvectorintcargo(container);vectorintcapacity(container);vectorintusedWeight(container,0);inttotalCapacity0;for(inti0;icontainer;i){cincapacity[i];totalCapacitycapacity[i];}intpackage,weight;inttotalWeight0,cargoWeight0,unusedWeight0,unloadedWeight0;boolworkingtrue;cinpackage;for(inti0;ipackage;i){cinweight;totalWeightweight;if(working){intbest0;for(intj1;jcontainer;j){if(cargo[j].size()cargo[best].size())bestj;else{if(cargo[j].size()cargo[best].size())if(capacity[j]capacity[best])bestj;}}if(capacity[best]weight){cargo[best].push_back(weight);capacity[best]-weight;cargoWeightweight;}else{unloadedWeightweight;workingfalse;}}elseunloadedWeightweight;}if(cases0)cout\n;intmaxPackage0;for(inti0;icontainer;i)maxPackagemax(maxPackage,(int)cargo[i].size());for(intimaxPackage-1;i0;i--){for(intj0;jcontainer;j){if(j0)cout ;if(icargo[j].size())coutcargo[j][i];elsecout:;}cout\n;}for(inti1;i(2*container-1);i)cout;cout\n;for(inti1;icontainer;i){if(i1)cout ;couti;}cout\n;cout\n;coutcargo weight: cargoWeight\n;coutunused weight: (totalCapacity-cargoWeight)\n;coutunloaded weight: unloadedWeight\n;}return0;}总结本题的关键在于准确实现货柜选择的优先级规则并注意装载终止后所有后续包裹均计入未装载重量。输出格式较为繁琐需要按层打印货柜内容空位用:表示并注意分隔线与编号行的对齐。时间复杂度为O(p×c)O(p \times c)O(p×c)空间复杂度为O(pc)O(p c)O(pc)能够高效处理题目规模的数据。