C++で配列要素の削除コストを最小限に抑えるアルゴリズム

問題の概要

N個の要素を持つ配列が与えられます。この配列から、以下のルールに従って要素を削除していきます。

操作の内容は次のとおりです。まず配列から任意の2つの数を選び、そのうち大きい方を削除します。このとき発生するコストは、小さい方の数と等しくなります。この操作を繰り返し、一度に1つの要素だけを削除しながら、全体のコストを最小化することが目標です。

例として、配列 {4, 2, 5} を考えてみましょう。まず 4 と 2 を選び、コスト 2 を支払って 4 を削除します。続いて残った 5 を、再びコスト 2 で削除します。

解法のアプローチ

この問題の解き方は非常にシンプルです。操作のコストは必ず「小さい方の数」になるため、コストを抑えるには配列内の最小値を活用するのが最適です。

具体的には、毎回「最小値」と「それ以外の任意の要素」のペアを選び、大きい方を削除します。こうすることで、各操作のコストは常に最小値となり、結果として総コストは次の式で求められます。

総コスト = (N − 1) × 最小値

要素を1つ削除するたびに配列のサイズが1ずつ減るため、削除操作は全部で N − 1 回行われます。したがって、上記の式で答えが導けます。

実装例(C++)

#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

計算量について

min_element による最小値の探索には O(N) の時間がかかりますが、その後の計算は定数時間で完了するため、全体の時間計算量は O(N)、空間計算量は O(1) となります。非常に効率的な解法と言えるでしょう。