C++でリストの値を等しくする最小操作回数を求める方法

整数のリスト nums があるとします。ここで、「リスト内のいくつかの整数（部分集合）を選び、選んだ値をすべて1つずつ増やす」という操作を考えます。この操作を繰り返してリスト内のすべての値を等しくするとき、必要となる最小の操作回数を求めるのが本問題です。

例えば、入力が [1,3,5] の場合、出力は 4 になります。

解法のポイント

一見複雑な問題に見えますが、実は答えはとてもシンプルで、リスト内の最大値と最小値の差がそのまま最小操作回数になります。

その理由は次のとおりです。1回の操作で増やせるのは選んだ要素だけなので、最小値の要素を最大値まで引き上げるには、少なくとも「最大値 − 最小値」回の操作が必要です。逆に、毎回の操作で「まだ最大値に達していない要素をすべて」増やしていけば、ちょうど「最大値 − 最小値」回ですべての要素を揃えることができます。したがって、これが最小操作回数となります。

アルゴリズムの手順

• nums のサイズが 1 の場合 → 0 を返す（要素が1つだけなら常に等しいため）
• ret := 0（結果を格納する変数）
• maxVal := -inf（最大値を格納する変数）
• minVal := inf（最小値を格納する変数）
• i を 0 から nums のサイズ未満まで1ずつ増やしながら、以下を繰り返す
  • maxVal := maxVal と nums[i] のうち大きい方
  • minVal := minVal と nums[i] のうち小さい方
• maxVal - minVal を返す

入力例の動きを確認

[1,3,5] の場合、次のように4回の操作で全体を揃えられます。

1. {1, 3} を選んで +1 → [2, 4, 5]
2. {2, 4} を選んで +1 → [3, 5, 5]
3. {3} を選んで +1 → [4, 5, 5]
4. {4} を選んで +1 → [5, 5, 5]

合計4回で完了しました。これは最大値 5 と最小値 1 の差（5 − 1 = 4）と一致しています。

理解を深めるために、以下のC++による実装例を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<int> &nums) {
        if (nums.size() == 1)
        return 0;
        int ret = 0;
        int maxVal = INT_MIN;
        int minVal = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            maxVal = max(maxVal, nums[i]);
            minVal = min(minVal, nums[i]);
        }
        return maxVal - minVal;
    }
};
main() {
    Solution ob;
    vector<int> v = {1,3,5};
    cout << (ob.solve(v));
}

入力

{1,3,5}

出力

4