首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

UVA Live 4636:邏輯推理求最少立方體數(正視圖+側視圖)

     編輯:關於C++

問題描述

等大立方體堆疊。給定正視圖(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。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved