標題:
202411潛力1-積木城堡 (Castle)
[打印本頁]
作者:
may
時間:
2024-12-27 12:28
標題:
202411潛力1-積木城堡 (Castle)
問題敘述
元元有非常多塊的積木，他用這些積木做了非常多不同形狀的建築物。這些建築物都是由數個直條組成，每個直條則是由數個立方體垂直堆疊而成。下方左圖所示的建築物由高度分別為3、2、1、1的四個直條所組成，而建築物的高度就是其組成中最高的直條所具有的高度。
[attach]20343[/attach]
有一天他突發奇想，希望可以將自己做的所有建築物拼接在一起變成一個超級大的城堡。他會不斷從現有的建築物挑選兩個建築物出來進行合併，直到最後剩下一個建築物時就是一個大城堡了。在合併時，他希望所合併的兩個建築的高度要相同；如果兩個建築物高度不同，則需要將高度較低的那一個建築物墊高。為了保持原本建築物的形狀，墊高時元元必須在每一個直條下方都增加相同數量的積木。如果要把上圖左邊高度 3 的建築物與某個高度5的建築物合併，就必須要在左邊建築物的每一個直條下方追加 2 塊積木將其墊高至高度5，也就是總共要追加8塊積木，變成如上圖右邊所示。 給定元元的建築物資訊，請幫忙計算若要將所有建築物合併成一個積木城堡，最少需要增加多少塊積木。 輸入格式 第一列有一個整數N (2 ≤ N ≤ 2×10
5
) 代表建築物的數量。接下來有 N 列，每一列一開始有一個整數 K，代表該座建築物由多少個部分所組成，接著有 K個正整數代表該建築物每一個部分的高度。保證建築物的直條數總和不超過10
6
，且每個直條的高度不超過10
9
。 輸出格式 請輸出一個整數，代表需要增加多少塊積木才能把所有建築物合併成一個。
[attach]20344[/attach]
評分說明 此題目測資分成二組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
[attach]20345[/attach]
作者:
may
時間:
2024-12-27 14:48
//#include<iostream>
//#include<vector>
//#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> building_size(N);//建築物的直線數
vector<int> building_height(N);//建築物的高度
int max_height = -1;
for(int i=0; i<N; ++i)
{
cin >> building_size[i];
int height = -1;
int K = building_size[i];
for(int j=0; j<K; ++j)
{
int s;
cin >> s;
height = max(height, s);//找建築物的高度
}
building_height[i] = height;
if(height>max_height)
max_height = height;//找出最高的建築物高度
}
long long ans = 0;//
for(int i=0; i<N; ++i)
{
ans += (long long)building_size[i] * (max_height-building_height[i]);
}
cout << ans << endl;
}
/*
6
7 4 6 1 2 4 2 5
6 11 8 4 2 3 6
4 3 2 5 2
5 4 4 4 4 4
3 12 15 10
1 7
*/
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2
