等大立方體堆疊。給定正視圖(C 列高度)和側視圖(R 行高度)。每個立方體只能放地面或另一立方體正上方。求最少立方體數。
正視圖給出每列最大高度,側視圖給出每行最大高度。最少立方體數 = max(正視圖總和, 側視圖總和) + 額外補充。
實際算法:
1. 計算兩視圖總和 sum1, sum2。
2. 以較大總和為基準,統計其每種高度出現次數 cnt[h]。
3. 遍歷另一視圖高度 h:若 cnt[h] > 0 則 cnt[h]--(共用該高度列);否則需新增 h 個立方體。
4. 答案 = 基準總和 + 新增總和。
#include
#include
int main() {
int c, r, a1[25], a2[25], cnt[25];
while (scanf("%d%d", &c, &r) == 2 && c) {
memset(cnt, 0, sizeof(cnt));
int sum1 = 0, sum2 = 0;
for (int i=0; i sum2) {
for (int i=0; i
正視圖:3 列高度 2,1,3 (sum=6);側視圖:2 行高度 3,2 (sum=5)。
基準 sum1=6,cnt[2]=1, cnt[1]=1, cnt[3]=1。
側視圖 3→cnt[3]--,2→cnt[2]--。無新增。答 6。
若側視圖有 4,則 cnt[4]=0 → sum1+=4=10。