【C++】アクセスするたびに最大値が減少する配列から最大値の合計を求める方法

この記事では、整数型の配列 arr[] と整数 M が与えられたとき、「アクセスするたびに最大値が1ずつ減少する」という条件のもとで、配列から取得できる最大値の合計を求めるプログラムをC++で作成します。

問題の説明

配列の中から最大要素を見つけ出し、それを取り出すたびに値を -1 して戻すという操作を M 回繰り返します。そして、M 回の取得で得られた値の合計を出力します。

具体例で問題を確認しましょう。

入力: arr[] = {3, 6, 8, 9}、M = 2

出力: 17

解説

1回目の操作: 最大値は 9。合計 = 9。更新後の配列 = {3, 6, 8, 8}

2回目の操作: 最大値は 8。合計 = 9 + 8 = 17。更新後の配列 = {3, 6, 7, 8}

したがって、M = 2 回のアクセスで得られる合計は 17 となります。

解決アプローチ

シンプルな解法としては、優先度付きキュー(最大ヒープ)を使用する方法があります。最大ヒープでは常に根(先頭)に最大要素が配置されるため、以下の手順で処理を行います。

1. 配列の全要素を最大ヒープに挿入します。
2. M 回にわたって、根の要素(最大値)を取り出し、合計に加算します。
3. 取り出した要素から 1 を引いた値を再びヒープに挿入します。
4. M 回の操作が完了したら、合計値を返します。

この方法では、各操作の計算量は O(log N) となるため、全体の計算量は O(M log N) となり、効率的に処理できます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int getSum(int arr[], int N, int M) {
    int sumVal = 0;
    priority_queue<int> heap;
    for (int i = 0; i < N; i++)
        heap.push(arr[i]);
    while (M--) {
        int maximumVal = heap.top();
        sumVal += maximumVal;
        heap.pop();
        heap.push(maximumVal - 1);
    }
    return sumVal;
}

int main() {
    int arr[] = { 3, 6, 8, 9 };
    int M = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "アクセスごとに最大値が減少する場合の合計値: " << getSum(arr, N, M);
}

出力結果

アクセスごとに最大値が減少する場合の合計値: 17

まとめ

本記事では、アクセスするたびに最大値が1ずつ減少する配列から、M 回の取得で得られる最大値の合計を求める問題を扱いました。C++ の priority_queue(最大ヒープ)を活用することで、O(M log N) の計算量で効率的に解くことができます。このパターンは、優先度付きキューを活用する他のアルゴリズム問題にも応用できるため、ぜひマスターしておきましょう。