Tìm số hộp cần loại bỏ trong C++

Trong bài toán này, chúng ta được cho một mảng arr[] trong đó mỗi phần tử đại diện cho một đống hộp (mỗi hộp cao 1 đơn vị). Nhiệm vụ của chúng ta là tìm số hộp cần loại bỏ.

Người đứng tại chỉ số 0 của mảng ở độ cao của đống hộp và cần di chuyển đến cuối mảng. Điều kiện để di chuyển từ đống này sang đống khác là nhảy sang đống tiếp theo.

Nhảy chỉ có thể khi đống tiếp theo cùng độ cao hoặc thấp hơn. Nếu đống tiếp theo cao hơn, người cần loại bỏ hộp từ đống tiếp theo cho đến khi độ cao bằng nhau. Ta cần tìm tổng số hộp bị loại bỏ khi đi từ đống đầu đến đống cuối.

Hãy xem ví dụ sau để hiểu bài toán:

Input : arr[] = {5, 7, 3 , 1, 2} Output : 3

Giải thích

Ban đầu, người ở độ cao 5.

Bước 1 − Đi đến vị trí thứ hai độ cao 7, cần loại bỏ 2 hộp.

Bước 2 − Đi đến vị trí thứ ba độ cao 3, không loại hộp.

Bước 3 − Đi đến vị trí tiếp theo độ cao 1, không loại hộp.

Bước 4 − Đi đến vị trí tiếp theo độ cao 2, loại 1 hộp. Tổng hộp loại bỏ = 3.

Phương pháp giải

Một giải pháp đơn giản là duyệt mảng từ đầu đến cuối và kiểm tra nếu phần tử tiếp theo lớn hơn hiện tại. Nếu có, cộng hiệu của chúng vào biến boxesRemoved chứa tổng số hộp sẽ bị loại bỏ. Cuối cùng trả về boxesRemoved.

Ví dụ

Chương trình minh họa cho giải pháp

#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; }

Kết quả

The total number of boxes to be removed to reach the end is 7