ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งแต่ละสมาชิกแทนกองกล่อง (แต่ละกล่องสูง 1 หน่วย) งานของเราคือ การหาจำนวนกล่องที่ต้องนำออก
บุคคลหนึ่งยืนที่ดัชนี 0 ของอาร์เรย์ ที่ระดับความสูงของกองกล่อง และต้องเดินไปถึงปลายอาร์เรย์ เงื่อนไขการเคลื่อนที่จากกองหนึ่งไปอีกกองคือการกระโดด
การกระโดดเป็นไปได้ก็ต่อเมื่อกองถัดไปมีความสูงเท่ากันหรือต่ำกว่า หากกองถัดไปสูงกว่า บุคคลนั้นต้องนำกล่องออกจากกองถัดไป จนกว่าความสูงจะเท่ากัน เราต้องหาจำนวนกล่องทั้งหมดที่จะถูกนำออกขณะเดินจากกองแรกไปกองสุดท้าย
ตัวอย่างเพื่อความเข้าใจ
Input : arr[] = {5, 7, 3, 1, 2}
Output : 3
คำอธิบาย
เริ่มต้น บุคคลอยู่ที่ความสูง 5
ขั้นตอนที่ 1 − ไปตำแหน่งที่ 2 ซึ่งมีความสูง 7 ต้องนำกล่องออก 2 กล่อง
ขั้นตอนที่ 2 − ไปตำแหน่งที่ 3 ความสูง 3 ไม่นำกล่องออก
ขั้นตอนที่ 3 − ไปตำแหน่งที่ 4 ความสูง 1 ไม่นำกล่องออก
ขั้นตอนที่ 4 − ไปตำแหน่งที่ 5 ความสูง 2 นำกล่องออก 1 กล่อง รวมทั้งหมด 3 กล่อง
แนวทางแก้ปัญหา
วิธีแก้ที่ง่ายคือเดินผ่านอาร์เรย์จากต้นจนจบ ตรวจสอบว่าสมาชิกถัดไปมากกว่าสมาชิกปัจจุบันหรือไม่ หากใช่ ให้บวกความต่างเข้าไปในตัวแปร boxesRemoved ซึ่งเก็บจำนวนกล่องทั้งหมดที่ต้องนำออก
ตัวอย่างโค้ด
#include <iostream>
using namespace std;
int findBoxesRemoved(int arr[], int n) {
int boxesRemoved = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1])
boxesRemoved += (arr[i + 1] - arr[i]);
}
return boxesRemoved;
}
int main() {
int arr[] = { 5, 7, 3, 1, 2, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The total number of boxes to be removed to reach the end is " << findBoxesRemoved(arr, n);
return 0;
}
ผลลัพธ์
The total number of boxes to be removed to reach the end is 7
