数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告