題目描述一艘船最多有999個(gè)貨柜編號(hào)為111到999每個(gè)貨柜有特定的最大承重能力不超過(guò)999999999噸。每個(gè)包裹重量不超過(guò)999噸船上最多裝載999999999個(gè)包裹。包裹通過(guò)傳送帶依次到達(dá)由貨物路由器按照以下算法分配到貨柜規(guī)則1\texttt{1}1. 首先只選擇裝載包裹數(shù)量最少的貨柜。規(guī)則2\texttt{2}2. 然后在選出的貨柜中只選擇可用承重能力最大的貨柜。規(guī)則3\texttt{3}3. 進(jìn)一步篩選選擇編號(hào)最小的貨柜。規(guī)則4\texttt{4}4. 如果選中的貨柜無(wú)法承載該包裹則裝船過(guò)程結(jié)束。要求模擬該裝載過(guò)程輸出每個(gè)貨柜的最終內(nèi)容、已裝載包裹總重量、剩余可用重量以及未裝載包裹總重量。輸入格式輸入包含多個(gè)測(cè)試用例用例之間用空行分隔。每個(gè)測(cè)試用例首先給出貨柜數(shù)量ccc1≤c≤91 \le c \le 91≤c≤9隨后ccc行給出每個(gè)貨柜的最大承重cwicwicwi1≤cwi≤9991 \le cwi \le 9991≤cwi≤999。接著是一個(gè)空行然后給出包裹數(shù)量ppp1≤p≤9991 \le p \le 9991≤p≤999隨后ppp行給出每個(gè)包裹的重量pwipwipwi1≤pwi≤91 \le pwi \le 91≤pwi≤9。保證所有包裹總重量不超過(guò)所有貨柜總承重。輸出格式對(duì)于每個(gè)測(cè)試用例輸出貨柜的最終內(nèi)容按從頂部到底部的順序每行對(duì)應(yīng)所有貨柜在同一層的內(nèi)容空位用:表示隨后是一個(gè)空行然后是已裝載包裹總重量、剩余可用重量和未裝載包裹總重量。相鄰測(cè)試用例之間輸出一個(gè)空行。樣例輸入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題目分析本題要求模擬一個(gè)按特定規(guī)則分配包裹的裝載過(guò)程。核心在于準(zhǔn)確實(shí)現(xiàn)四條選擇規(guī)則并正確處理裝載終止條件。貨柜數(shù)量最多為999包裹數(shù)量最多為999999999因此直接模擬即可無(wú)需復(fù)雜優(yōu)化。規(guī)則1\texttt{1}1要求選擇裝載包裹數(shù)量最少的貨柜。規(guī)則2\texttt{2}2在規(guī)則1\texttt{1}1的基礎(chǔ)上選擇可用承重最大的貨柜。規(guī)則3\texttt{3}3在規(guī)則2\texttt{2}2的基礎(chǔ)上選擇編號(hào)最小的貨柜。規(guī)則4\texttt{4}4檢查選中的貨柜是否能承載當(dāng)前包裹若能則裝入并更新貨柜狀態(tài)若不能則裝載過(guò)程立即終止后續(xù)所有包裹均視為未裝載。輸出格式較為特殊需要將每個(gè)貨柜的內(nèi)容按從頂部到底部的順序逐層打印每層對(duì)應(yīng)所有貨柜在該層的內(nèi)容若某貨柜在該層沒(méi)有包裹則輸出:。分隔線由2c?12c - 12c?1個(gè)等號(hào)組成貨柜編號(hào)行由111到ccc組成。解題思路使用二維向量cargo存儲(chǔ)每個(gè)貨柜已裝載的包裹重量其中cargo[i]表示第iii個(gè)貨柜的包裹列表按裝入順序排列。使用數(shù)組capacity記錄每個(gè)貨柜的剩余可用承重初始值為最大承重。使用布爾變量working標(biāo)記裝載過(guò)程是否仍在進(jìn)行。對(duì)于每個(gè)包裹若working為真則遍歷所有貨柜按照規(guī)則1\texttt{1}1到規(guī)則3\texttt{3}3選出最佳貨柜。具體比較邏輯為優(yōu)先比較包裹數(shù)量越少越優(yōu)若數(shù)量相同比較剩余承重越大越優(yōu)若仍相同比較編號(hào)越小越優(yōu)。選出最佳貨柜后檢查其剩余承重是否大于等于當(dāng)前包裹重量若是則裝入包裹更新剩余承重和已裝載總重量若否則將當(dāng)前包裹計(jì)入未裝載重量并將working置為假。若working已為假則直接將包裹計(jì)入未裝載重量。所有包裹處理完畢后計(jì)算每個(gè)貨柜的最大包裹數(shù)量maxPackage然后從最高層到最低層逐層輸出。對(duì)于每一層遍歷所有貨柜若該貨柜在該層有包裹則輸出包裹重量否則輸出:。層間用空格分隔。之后輸出分隔線、貨柜編號(hào)行、空行以及三個(gè)統(tǒng)計(jì)量。時(shí)間復(fù)雜度為O(p×c)O(p \times c)O(p×c)空間復(fù)雜度為O(pc)O(p c)O(pc)對(duì)于題目規(guī)模完全可行。代碼實(shí)現(xiàn)// Loading a Cargo Ship// UVa ID: 945// Verdict: Accepted// Submission Date: 2017-03-14// UVa Run Time: 0.000s//// 版權(quán)所有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;}總結(jié)本題的關(guān)鍵在于準(zhǔn)確實(shí)現(xiàn)貨柜選擇的優(yōu)先級(jí)規(guī)則并注意裝載終止后所有后續(xù)包裹均計(jì)入未裝載重量。輸出格式較為繁瑣需要按層打印貨柜內(nèi)容空位用:表示并注意分隔線與編號(hào)行的對(duì)齊。時(shí)間復(fù)雜度為O(p×c)O(p \times c)O(p×c)空間復(fù)雜度為O(pc)O(p c)O(pc)能夠高效處理題目規(guī)模的數(shù)據(jù)。