資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢給定物件陣列中的最大高度金字塔
假設我們有一個包含 n 個物件的陣列。每個物件都有寬度 W[i]。我們必須以金字塔的方式排列它們，例如 -
第 i 層的總寬度小於第 (i + 1) 層
第 i 層的物件總數小於第 (i + 1) 層
例如，如果權重為 [40, 100, 20, 30]，則輸出為 2。所以頂層是 30，然後下一層是 20、40 和 100
為了解決這個問題，我們將使用貪婪演算法。其思想是將寬度較小的物件放在頂部，下一個物件放在正下方的層，依此類推。為了獲得最大層數，對給定陣列進行排序並嘗試從上到下形成金字塔。
然後找到陣列中最小的元素，例如排序後陣列的第一個元素，將其放在頂部。然後嘗試在其下方用更多物件和更大寬度構建層。
示例
#include <iostream>
#include <algorithm>
using namespace std;
int maxLevelPyramid(int objects[], int n) {
sort(objects, objects + n);
int ans = 1;
int prev_w = objects[0];
int count_p = 1;
int count_c = 0;
int curr_w = 0;
for (int i=1; i<n; i++){
curr_w += objects[i];
count_c++;
if (curr_w > prev_w && count_c > count_p){
prev_w = curr_w;
count_p = count_c;
count_c = curr_w = 0;
ans++;
}
}
return ans;
}
int main() {
int boxes[] = {40, 100, 20, 30};
int n = sizeof(boxes)/sizeof(boxes[0]);
cout << "Max level of pyramid: " << maxLevelPyramid(boxes, n);
}輸出
Max level of pyramid: 2
更新於: 2020年1月3日
628 次檢視
廣告