Giả sử chúng ta có một mảng với N phần tử. Chúng ta phải xóa phần tử khỏi mảng bằng cách thực hiện theo các phép toán đã cho. Hoạt động này giống như, chúng ta phải chọn hai số bất kỳ của mảng và loại bỏ lớn hơn. Chi phí bao gồm trong hoạt động này giống như con số nhỏ hơn. Chúng tôi chỉ phải xóa một phần tử tại một thời điểm, dựa trên thao tác này và thực hiện tác vụ với chi phí tối thiểu. Giả sử mảng có {4, 2, 5}. Tôi lấy 4 và 2, loại bỏ 4 bằng cách trả chi phí 2, sau đó chúng tôi loại bỏ 5 một lần nữa với chi phí 2.
Cách tiếp cận quá đơn giản. Như chúng ta biết rằng chi phí sẽ giống như chi phí nhỏ hơn, vì vậy để giảm chi phí, chúng tôi sẽ lấy một yếu tố nhỏ nhất, và một số yếu tố khác, sau đó loại bỏ yếu tố lớn hơn, chi phí sẽ luôn nhỏ hơn. Vì vậy, tổng chi phí sẽ là (N - 1) * con số nhỏ nhất.
Ví dụ
#include <iostream>
#include <algorithm>
using namespace std;
int getMinimumCost(int arr[], int n) {
int smallest = *min_element(arr, arr+n);
return smallest * (n - 1);
}
int main() {
int arr[] = { 4, 2, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum cost: " << getMinimumCost(arr, n);
} Đầu ra
Minimum cost: 4