ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งแต่ละองค์ประกอบแสดงถึงกองกล่อง (ความสูงของแต่ละหน่วย) งานของเราคือ ค้นหาจำนวนกล่องที่จะลบ .
บุคคลนั้นยืนอยู่ที่ดัชนี 0 ของอาร์เรย์ที่ความสูงของกองกล่อง และเขาต้องย้ายไปที่ส่วนท้ายของอาร์เรย์ เงื่อนไขการย้ายจากกองหนึ่งไปอีกกองคือการกระโดดไปยังกองถัดไป
กระโดดได้ก็ต่อเมื่อกองถัดไปอยู่ที่ความสูงเท่ากันหรือสูงน้อยกว่านั้น ถ้าความสูงของกองถัดไปมากกว่า บุคคลนั้นจำเป็นต้องเอากล่องออกจากกองถัดไป จนกว่าความสูงจะเท่ากัน เราต้องหาจำนวนกล่องทั้งหมดที่จะลบออกจากกล่องแรกไปกล่องสุดท้าย
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : arr[] = {5, 7, 3 , 1, 2}
Output : 3 คำอธิบาย
เริ่มแรกบุคคลนั้นสูง 5.
ขั้นตอนที่ 1 − ในการขึ้นสู่ตำแหน่งที่สองซึ่งมีความสูง 7 ระดับ บุคคลนั้นจะต้องนำกล่อง 2 กล่องออก
ขั้นตอนที่ 2 − หากต้องการไปยังตำแหน่งที่สามที่ความสูง 3 จะไม่มีการนำกล่องออก
ขั้นตอนที่ 3 − หากต้องการไปยังตำแหน่งถัดไปที่ความสูง 1 จะไม่มีการนำกล่องออก
ขั้นตอนที่ 4 − หากต้องการไปยังตำแหน่งถัดไปที่ความสูง 2 กล่องหนึ่งกล่องจะถูกลบออก ทำให้จำนวนกล่องที่เอาออกเท่ากับ 3
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสำรวจอาร์เรย์ตั้งแต่ต้นจนจบและตรวจสอบว่าองค์ประกอบถัดไปมีค่ามากกว่าองค์ประกอบปัจจุบันหรือไม่ ถ้าใช่ ให้เพิ่มส่วนต่างลงใน boxesRemoved ตัวแปรที่มีจำนวนกล่องทั้งหมดที่จะลบออก ในที่สุด เราจะคืน 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
