題意:等大的立方體搭積木,每個立方體可以直接放在地上或放在另一個正方體的正上方,給出正視圖和側視圖,問最少要用多少個正方體。
題解:可以先想如何形成正視圖或側視圖,那麼就是二維平面,正視圖(側視圖)上有多少個正方形就是有多少個正方體,然後在這個基礎上側視圖(正視圖)如果出現新的列(之前視圖不相等)的,就要新擺放一個,否則通過平移可以看做同一列,就不需要添加正方體了,那麼可以得出,最少數量正方體就是正視圖或側視圖中正方形多的那個視圖,把它上面的正方形數量加上另一個視圖上沒有出現過的所有列就是最終解,用一個map就能解決。
#include#include const int N = 25; int c, r, m[N], a1[N], a2[N]; int main() { while (scanf("%d%d", &c, &r) && c) { memset(m, 0, sizeof(m)); int sum1 = 0, sum2 = 0; for (int i = 0; i < c; i++) { scanf("%d", &a1[i]); sum1 += a1[i]; } for (int i = 0; i < r; i++) { scanf("%d", &a2[i]); sum2 += a2[i]; } if (sum1 > sum2) { for (int i = 0; i < c; i++) m[a1[i]]++; for (int i = 0; i < r; i++) if (!m[a2[i]]) sum1 += a2[i]; else m[a2[i]]--; printf("%d\n", sum1); } else { for (int i = 0; i < r; i++) m[a2[i]]++; for (int i = 0; i < c; i++) if (!m[a1[i]]) sum2 += a1[i]; else m[a1[i]]--; printf("%d\n", sum2); } } return 0; }