C++ですべてのタスク完了に必要な最小時間を求めるアルゴリズム

n個の要素を持つ配列Aと、2つの整数kおよびxが与えられているとします。i番目のタスクを完了するには通常A[i]の時間がかかります。配列Aは非降順(昇順)にソートされているものとします。ここで、Amalは最大k個までのタスクを選び、それらを本来のA[i]の代わりにx単位の時間で実行できるものとします(ただし、xは配列内の最小値よりも小さい値です)。このとき、Amalがすべてのタスクを完了するために必要な最小時間を求めるのが目的です。なお、複数のタスクを同時に実行することはできません。

例として、入力が A = [3, 6, 7, 10]、k = 2、x = 2 の場合を考えてみましょう。この場合の出力は 13 になります。最適な戦略は、3番目と4番目のタスクを選び、本来のA[2]とA[3]の代わりにそれぞれx = 2の時間で処理することです。したがって、答えは 3 + 6 + 2 + 2 = 13 となります。

解法のアプローチ

この問題は貪欲法(グリーディ法)で効率的に解くことができます。配列Aがソートされているため、最も時間のかかるタスクから順に短縮対象として選ぶのが最適です。具体的には以下の手順で計算します。

1. x を k × x に更新します(短縮後の合計時間)。
2. n を配列Aのサイズとします。
3. i を 0 から n - k - 1 まで繰り返し処理を行います:
   • t に A[i] を代入します。
   • x に t を加算します。
4. 最終的な x を結果として返します。

つまり、短縮できない最初の n - k 個のタスクの合計時間に、短縮後の k 個分の時間(k × x)を加えたものが答えになります。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k, int x){
    x = k * x;
    int n = A.size();
    for (int i = 0; i < n - k; i++){
        int t = A[i];
        x += t;
    }
    return x;
}
int main(){
    vector<int> A = { 3, 6, 7, 10 };
    int k = 2;
    int x = 2;
    cout << solve(A, k, x) << endl;
}

入力

{ 3, 6, 7, 10 }, 2, 2

出力

13

計算量について

このアルゴリズムの時間計算量はO(n)です。配列を一度走査するだけで済むため、非常に効率的です。空間計算量もO(1)であり、追加のメモリをほとんど必要としません。ソート済みの配列という前提条件があるため、貪欲に大きい要素から置き換えることで最適解が保証されます。