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