C++で配列の全要素がK以上になるまで最小要素を加算する方法

配列（Array）とは、同じデータ型の要素を格納するコンテナであり、各要素は0から始まるインデックスで管理されます。

この記事では、整数型の配列を扱い、配列内のすべての要素が指定された数値以上であるかどうかを確認します。具体的には、配列のすべての要素が与えられた数値 K 以上になっているかを判定し、条件を満たしていない場合は、配列内で最も小さい2つの要素を取り出して合計し、その合計値を1つの新しい要素として扱います。その後、再び同じ条件で新しい配列をチェックします。条件が満たされれば、加算を実行した回数を結果として返します。

問題例

Array = { 2, 6, 3, 12, 7 }　K = 5
Output : 1

解説

まず、すべての要素が K 以上かどうかを確認します。この例では条件を満たしていないため、最も小さい2つの数値「2」と「3」を加算します。すると、新しい配列の最初の要素は「5」になります。再度条件を確認すると、今度はすべての要素が K 以上となっているため、実行した加算回数である「1」を返します。

アルゴリズム

入力：配列と数値 K

Step 1 : すべての要素が K 以上かどうかを確認する
Step 2: if(はい){
    反復回数を出力する。
}
exit(0)
Step 3: else {
    配列内の最も小さい2つの要素を加算し、1つの要素としてまとめる。
}
Step 4: Step 1 へ戻る

このアルゴリズムを効率的に実装するには、最小ヒープ（Min Heap）データ構造を使用するのが効果的です。最小ヒープを使えば、常に最小の要素を O(log n) の計算量で取り出すことができます。

実装例（C++）

#include<bits/stdc++.h>
using namespace std;
class MinHeap{
   int *harr;
   int capacity;
   int heap_size;
   public:
   MinHeap(int *arr, int capacity);
   void heapify(int );
   int parent(int i){
      return (i-1)/2;
   }
   int left(int i){
      return (2*i + 1);
   }
   int right(int i){
      return (2*i + 2);
   }
   int extractMin();
   int getMin(){
      return harr[0];
   }
   int getSize(){
      return heap_size;
   }
   void insertKey(int k);
};
MinHeap::MinHeap(int arr[], int n){
   heap_size = n;
   capacity = n;
      harr = new int[n];
   for (int i=0; i<n; i++)
      harr[i] = arr[i];
   for (int i=n/2-1; i>=0; i--)
      heapify(i);
}
void MinHeap::insertKey(int k){
   heap_size++;
   int i = heap_size - 1;
   harr[i] = k;
   while (i != 0 && harr[parent(i)] > harr[i]){
      swap(harr[i], harr[parent(i)]);
      i = parent(i);
   }
}
int MinHeap::extractMin(){
   if (heap_size <= 0)
      return INT_MAX;
   if (heap_size == 1){
      heap_size--;
      return harr[0];
   }
   int root = harr[0];
   harr[0] = harr[heap_size-1];
   heap_size--;
   heapify(0);
   return root;
}
void MinHeap::heapify(int i){
   int l = left(i);
   int r = right(i);
   int smallest = i;
   if (l < heap_size && harr[l] < harr[i])
      smallest = l;
   if (r < heap_size && harr[r] < harr[smallest])
      smallest = r;
   if (smallest != i){
      swap(harr[i], harr[smallest]);
      heapify(smallest);
   }
}
int main(){
   int arr[] = { 2, 6,3,12, 7};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 5;
   MinHeap h(arr, n);
   long int res = 0;
   while (h.getMin() < k){
      if (h.getSize() == 1)
         return -1;
      int first = h.extractMin();
      int second = h.extractMin();
      h.insertKey(first + second);
      res++;
   }
   cout << res;
   return 0;
}

実行結果

1

処理の流れのポイント

• getMin()：ヒープの先頭（最小値）を参照し、すべての要素が K 以上になったかを判定します。
• extractMin()：最小の要素を2つ取り出します。要素が1つしか残っておらず条件を満たさない場合は -1 を返して終了します。
• insertKey()：取り出した2つの要素の合計を新しい要素としてヒープに挿入し直します。

このように最小ヒープを活用することで、毎回配列全体を走査して最小値を探す非効率な手法と比べ、大幅に計算コストを抑えられます。全体の時間計算量は O(n log n) となります。