Trong bài toán này, chúng ta được cung cấp một mảng arr [] trong đó mỗi phần tử đại diện cho một đống hộp (mỗi hộp có chiều cao đơn vị). Nhiệm vụ của chúng ta là tìm số hộp cần loại bỏ .
Người đó đang đứng ở chỉ số 0 của mảng bằng chiều cao của đống hộp và anh ta cần di chuyển đến cuối mảng. Điều kiện để chuyển từ cọc này sang cọc tiếp theo là nhảy sang cọc tiếp theo.
Chỉ có thể nhảy khi cọc tiếp theo có cùng độ cao hoặc ở độ cao nhỏ hơn cọc. Nếu chiều cao của đống tiếp theo lớn hơn thì người đó cần loại bỏ các hộp từ đống tiếp theo, cho đến khi chiều cao bằng nhau. Chúng ta cần tìm tổng số hộp sẽ bị loại bỏ khi đi từ hộp đầu tiên đến hộp cuối cùng.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {5, 7, 3 , 1, 2}
Output : 3 Giải thích
Ban đầu, người đó có chiều cao là 5.
Bước 1 - Để đi đến vị trí thứ hai có 7 độ cao thì người đó cần lấy đi 2 ô.
Bước 2 - Để đi đến vị trí thứ ba ở độ cao 3, không có hộp nào bị xóa.
Bước 3 - Để đi đến vị trí tiếp theo ở độ cao 1, không có hộp nào bị xóa.
Bước 4 - Để đi đến vị trí tiếp theo ở độ cao 2, một hộp được lấy ra. Điều này làm cho số hộp bị loại bỏ bằng 3.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là duyệt qua mảng từ đầu đến cuối và kiểm tra xem phần tử tiếp theo có lớn hơn phần tử hiện tại hay không. Nếu có, hãy thêm sự khác biệt của chúng vào các hộp Đã xóa biến chứa tổng số hộp sẽ bị xóa. Cuối cùng, chúng tôi sẽ trả lại hộp Đã xóa .
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The total number of boxes to be removed to reach the end is 7