C++で許可されている他のものとの交換でコストを最小限に抑える

N個の要素を持つ配列があるとします。与えられた操作に従って、配列から要素を削除する必要があります。操作は、配列の任意の2つの数値を選択し、大きい方を削除する必要があるようなものです。この操作に含まれるコストは、小さい方の数と同じです。この操作に基づいて、一度に1つの要素のみを削除し、最小限のコストでタスクを実行する必要があります。配列に{4、2、5}があるとします。私は4と2を取り、コスト2を支払って4を削除し、次にコスト2で5を削除します。

アプローチは単純すぎます。コストは小さいものと同じになることがわかっているので、コストを削減するために、小さいものと他の要素を取り、大きいものを削除すると、常に小さいものになります。したがって、総コストは（N – 1）*最小数になります。

例

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

出力

Minimum cost: 4