Tối thiểu chi phí xóa phần tử mảng bằng cách chọn cặp và xóa số lớn hơn trong C++

Cho mảng N phần tử. Cần xóa các phần tử bằng phép toán: chọn hai số, xóa số lớn hơn, chi phí bằng số nhỏ hơn. Chỉ xóa một phần tử mỗi lần. Tìm chi phí tối thiểu để xóa hết mảng. Ví dụ mảng {4, 2, 5}: chọn (4,2) xóa 4 chi phí 2, sau đó chọn (5,2) xóa 5 chi phí 2. Tổng chi phí = 4.

Giải pháp: Luôn chọn phần tử nhỏ nhất và một phần tử khác, xóa phần tử lớn hơn. Chi phí luôn bằng phần tử nhỏ nhất. Tổng chi phí = (N - 1) * phần tử nhỏ nhất.

Ví dụ minh họa

#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 << "Chi phi toi thieu: " << getMinimumCost(arr, n);
    return 0;
}

Kết quả

Chi phi toi thieu: 4