C++ プログラム: すべてのギフトの数量を等しくするために必要な操作の数を数えます。

それぞれサイズが n の 2 つの配列 A と B があるとします。プレゼントは n 個あり、何人かの子供たちに贈りたいと思っています。 i 番目のギフトは、A[i] キャンディーと B[i] オレンジで構成されます。移動中に、いくつかのギフトを選択し、次のアクションのいずれかを実行できます -

• そのギフトからキャンディーを取り出します (ある場合); p>

• このギフトからオレンジを 1 つ取り出します (ある場合);

• このギフトからキャンディーとオレンジのギフトを 1 つ取り出します (ある場合)。

#すべての贈り物は平等に作成される必要があります。これは、一連の動きの後、次の 2 つの動作が行われることを意味します。 次の条件が満たされる必要があります: A[0] = A[1] = ... = A[n-1] および B[0] = B[1] = ... = B[n-1]。私たちはしなければならない 与えられたすべての贈り物を平等にするために必要な最小ステップ数を見つけます。

問題カテゴリ

上記の問題は、貪欲な問題解決手法を適用することで解決できます。 貪欲なアルゴリズム技術は、現在最適なソリューションを提供するアルゴリズムのタイプです 考えられるすべての解決策を試すのではなく、選択してください。貪欲なアルゴリズム技術も 兄貴分の動的プログラミングと同様に、最適化問題を解決するために使用されます。アクティブ プログラミングするときは、考えられるすべてのサブ問題を調べて、最適なサブ問題を見つける必要があります。 解決策ですが、より多くの時間とスペースが必要になるという欠点があります。したがって、さまざまな シナリオ貪欲テクニックは、問題に対する最適な解決策を見つけるために使用されます。それは本当ですが すべての状況で最適な解決策が得られるわけではありませんが、慎重に設計すれば、より速く解決策を生み出すことができます。 動的プログラミングの問題。貪欲な手法で局所的な最適解を提供 最適化。この手法の例としては、Kruskal と Prim の最小関数が挙げられます。 スパニング ツリー (MST) アルゴリズム、ハフマン ツリー コーディング、ダイクストラの単一ソース最短パス 質問など

https://www.tutorialspoint.com/data_structurals_algorithms/greedy_algorithms.htm

https://www.tutorialspoint.com/data_structurals_algorithms/dynamic_programming.htm

p>したがって、問題への入力が A = [3, 5, 6]; B = [3, 2, 3] の場合、出力は 6 になります。 最初は B から取得されたため、B[0] は [2, 2, 3] になり、さらに A[1] から取得されるため、A = [3, 4, 6]、次に再び A[1] から、つまり A = [3, 3, 6]、次に A[2] と B[2] から、次のようになります。 [3, 3, 5] と [2, 2, 2]、次に A[2] から A = [3, 3, 4]、再び A[2] から [3, 3, 3] とします。つまり、A は同じ数のキャンディーを持ち、B は同じ数のオレンジを持っています。

手順

この問題を解決するには、次の手順に従います-

minA := inf
minB := inf
kq := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   minA := minimum of minA and A[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   minB := minimum of minB and B[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   kq := kq + maximum of (A[i] - minA) and (B[i] - minB)
return kq

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B){
   int minA = 999, minB = 999, kq = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      minA = min(minA, A[i]);
   for (int i = 0; i < n; i++)
      minB = min(minB, B[i]);
   for (int i = 0; i < n; i++)
      kq += max(A[i] - minA, B[i] - minB);
   return kq;
}
int main(){
   vector<int> A = { 3, 5, 6 };
   vector<int> B = { 3, 2, 3 };
   cout << solve(A, B) << endl;
}

入力

{ 3, 5, 6 }, { 3, 2, 3 }

出力

6

以上がC++ プログラム: すべてのギフトの数量を等しくするために必要な操作の数を数えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。