ปัญหา
กำหนดอาร์เรย์ของ n วัตถุ แต่ละวัตถุมีความกว้าง W[i] จงจัดเรียงให้เป็นรูปพีระมิดที่:
- ความกว้างรวมของระดับ i น้อยกว่าระดับ i+1
- จำนวนวัตถุในระดับ i น้อยกว่าระดับ i+1
ตัวอย่าง: ความกว้าง [40, 100, 20, 30] ผลลัพธ์คือ 2 ระดับ (ด้านบนคือ 30, ด้านล่างคือ 20, 40, 100)
แนวคิดแบบ Greedy
จัดวัตถุที่มีความกว้างน้อยกว่าอยู่ด้านบน วัตถุถัดไปอยู่ระดับด้านล่าง และทำต่อไป ให้จัดเรียงอาร์เรย์จากน้อยไปมาก แล้วสร้างพีระมิดจากบนลงล่าง
ขั้นตอน
- จัดเรียงอาร์เรย์จากน้อยไปมาก
- นำสมาชิกแรก (น้อยที่สุด) วางเป็นจุดสูงสุด
- สร้างระดับด้านล่างโดยใช้วัตถุมากขึ้นและมีความกว้างรวมมากขึ้น
โค้ดตัวอย่าง
#include <iostream>
#include <algorithm>
using namespace std;
int maxLevelPyramid(int objects[], int n) {
sort(objects, objects + n);
int ans = 1;
int prev_width = objects[0];
int prev_count = 1;
int curr_width = 0;
int curr_count = 0;
for (int i = 1; i < n; i++) {
curr_width += objects[i];
curr_count++;
if (curr_width > prev_width && curr_count > prev_count) {
prev_width = curr_width;
prev_count = curr_count;
curr_count = curr_width = 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
