C ++で指定された操作を使用して、配列を単一の整数に縮小します

---

入力として整数変数Numberを指定します。 1からNumberの範囲の要素を任意の順序で含む配列を考えてみましょう。

のような配列に対して1回の操作を実行すると

• 配列から2つの要素AとBを選択します

• アレイからAとBを削除します

• AとBの二乗和を配列に追加します

最後に単一の整数値を取得します。目標は、その要素の可能な最大値を見つけることです。

優先キューの使用

• 最終結果を最大化するには、最大になるようにAとBを選択する必要があります。

• 最大のAとBを見つけるために、優先度付きキューを使用して、その中に要素の値を格納します。

• 優先キューは要素を降順で格納します。

• 最上位の要素は、値などで最大です。したがって、2つの要素をポップした後、それらの正方形を再びキューにプッシュします。

• 数字をポップしてプッシュします-1回押して、目的の結果を取得します。

例

入力 −数値=2

出力 −配列縮小後の単一要素：5

説明 −配列に[1 2]

の要素があるとします。

優先キューに挿入した後-：2 1

A =5、B =4：A ² + B ² =1 + 4 =5

最後の要素：5

入力 −番号=5

出力 −配列縮小後の単一要素：5

説明 − [5 1 2 4 3]

のように配列に要素があるとします。

優先キューに挿入した後-：5 4 3 2 1

A =5、B =4：A ² + B ² =25 + 16 =41：41 3 2 1

A =41、B =3：A ² + B ² =1681 + 9 =1690：1690 2 1

A =1690、B =2：A ² + B ² =1681 + 4 =2856104：2856104 1

A =2856104、B =1：A ² + B ² =1187163712 + 1 =1187163713：1187163713

最後の要素：1187163713

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、キューに優先順位を付けて、配列の要素を降順で格納します。上位2つの最大の要素をポップし、両方の2乗の合計をそのキューに再度プッシュします。値が1つだけ残るまでこれを行います。

• 入力変数Numberを取得します。

• 結果のデータ型をlonglong整数として取得します-lli

• 関数reduceArray（int Num）は入力番号を受け取り、上記の操作を使用して計算された最大の単一整数を返します。

• 優先キューをpQueueとして取得します。

• whileループを使用して、pQueueに1からNまでの数値を入力します。

• i <=Numの間に、iをpQueueにプッシュ

• これで、pQueueの整数は1からNの降順で、サイズはNになります。

• 次に、サイズが>=1になるまでwhileループを使用してpQueueをトラバースします。

• 最大値をvar1=pQueue.top（）として取得し、ポップします。

• 次の最大値をvar2=pQueue.top（）として取得し、ポップします。

• var1を正方形、var2を正方形に設定します。

• var1+var2をpQueueに再度プッシュします。

• whileループの最後で、一番上の要素を返します。

• 結果をメイン内に印刷します。

例

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
   priority_queue<lli> pQueue;
   int i=1;
   while(i<=Num){
      pQueue.push(i);
      i=i+1;
   }
   while (pQueue.size() > 1) {
      lli var1 = pQueue.top();
      pQueue.pop();
      lli var2 = pQueue.top();
      pQueue.pop();
      var1=var1*var1;
      var2=var2*var2;
      pQueue.push(var1+var2);
   }
   return pQueue.top();
}
int main(){
   int Number = 5;
   cout<<"Single element after array reduction: "<<reduceArray(Number);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Single element after array reduction: 1187163713