202411潛力1-積木城堡 (Castle)

may

問題敘述
元元有非常多塊的積木，他用這些積木做了非常多不同形狀的建築物。這些建築物都是由數個直條組成，每個直條則是由數個立方體垂直堆疊而成。下方左圖所示的建築物由高度分別為3、2、1、1的四個直條所組成，而建築物的高度就是其組成中最高的直條所具有的高度。

有一天他突發奇想，希望可以將自己做的所有建築物拼接在一起變成一個超級大的城堡。他會不斷從現有的建築物挑選兩個建築物出來進行合併，直到最後剩下一個建築物時就是一個大城堡了。在合併時，他希望所合併的兩個建築的高度要相同；如果兩個建築物高度不同，則需要將高度較低的那一個建築物墊高。為了保持原本建築物的形狀，墊高時元元必須在每一個直條下方都增加相同數量的積木。如果要把上圖左邊高度 3 的建築物與某個高度5的建築物合併，就必須要在左邊建築物的每一個直條下方追加 2 塊積木將其墊高至高度5，也就是總共要追加8塊積木，變成如上圖右邊所示。 給定元元的建築物資訊，請幫忙計算若要將所有建築物合併成一個積木城堡，最少需要增加多少塊積木。 輸入格式 第一列有一個整數N (2 ≤ N ≤ 2×105 ) 代表建築物的數量。接下來有 N 列，每一列一開始有一個整數 K，代表該座建築物由多少個部分所組成，接著有 K個正整數代表該建築物每一個部分的高度。保證建築物的直條數總和不超過106，且每個直條的高度不超過109。 輸出格式 請輸出一個整數，代表需要增加多少塊積木才能把所有建築物合併成一個。

評分說明 此題目測資分成二組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。

may

1. //#include<iostream>
   
2. //#include<vector>
   
3. //#include<algorithm>
   
4. #include<bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. int main()
   
8. {
   
9.     int N;
   
10.     cin >> N;
    
11.     vector<int> building_size(N);//建築物的直線數
    
12.     vector<int> building_height(N);//建築物的高度
    
13.     int max_height = -1;
    
14.     for(int i=0; i<N; ++i)
    
15.     {
    
16.         cin >> building_size[i];
    
17.         int height = -1;
    
18.         int K = building_size[i];
    
19.         for(int j=0; j<K; ++j)
    
20.         {
    
21.             int s;
    
22.             cin >> s;
    
23.             height = max(height, s);//找建築物的高度
    
24.         }
    
25.         building_height[i] = height;
    
26.         if(height>max_height)
    
27.             max_height = height;//找出最高的建築物高度
    
28.     }
    
29.     long long ans = 0;//
    
30.     for(int i=0; i<N; ++i)
    
31.     {
    
32.         ans += (long long)building_size[i] * (max_height-building_height[i]);
    
33.     }
    
34.     cout << ans << endl;
    
35. }
    
36. /*
    
37. 6
    
38. 7 4 6 1 2 4 2 5
    
39. 6 11 8 4 2 3 6
    
40. 4 3 2 5 2
    
41. 5 4 4 4 4 4
    
42. 3 12 15 10
    
43. 1 7
    
44. */

複製代碼