指定された操作を実行した後に可能な配列の合計の最大値

この質問では、配列要素に対して指定された操作を実行し、最終的な最大合計を求めます。

ここでは、各操作で配列から最大 X[p] 要素を選択し、それらを Y[p] 要素に置き換えることで合計を最大化できます。

単純なアプローチでは、Y[p] 要素よりも小さい X[p] 配列要素を見つけて、それらを Y[p] に置き換えます。

効率的なアプローチでは、優先キューを使用して最大合計を取得します。

問題ステートメント- N 個の数値を含む nums[] 配列が与えられます。同時に、M 個の整数を含む X[] 配列と Y[] 配列が与えられます。 nums[] 配列に対して次の操作を実行する必要があります。

• X[] 要素と Y[] 要素の各要素に対して M 回の操作を実行する必要があります。各操作では、配列 nums[] から最大の X[p] 要素を選択し、それを Y[p] に置き換える必要があります。

与えられたタスクは、M 回の操作を実行した後、nums[] 配列の要素の最大合計を見つけることです。

例例

＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明 - 各操作を 1 つずつ実行してみましょう。

最初の操作では、7 つの要素を 500 に置き換えます。したがって、配列は {10, 8, 500, 60, 20, 18, 30, 60} になります。

2 番目の操作では、最大 2 つの要素を 10 に置き換えることができますが、10 未満の要素は 1 つだけです。したがって、8 を 10 に置き換えると、配列は {10, 10, 500, 60, 20, 18, 30, 60} になります。

• 3 番目の操作では、最大 5 つの要素を 2 つの要素に置き換えることができますが、配列には 2 未満の要素はありません。したがって、要素を置き換えることはありません。

• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- y[] 配列のすべての要素は、元の配列の要素よりも小さくなります。したがって、最大合計を取得するために、指定された配列の要素を置換する必要はありません。
• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
  説明
- ここでは、各操作で最大 x[p] 要素を置き換えることができます。最後の操作では、配列内の各要素を 100 に置き換えることができ、最大合計は 100 になります。

方法 1 このメソッドでは、x[] 配列と y[] 配列を反復処理します。各反復では、配列をソートして、y[p] 要素より小さい最大 x[p] 個の配列要素を取得し、それらを y[p] に置き換えます。

＃＃＃アルゴリズム＃＃＃

ステップ 1 - 「maxSum」を 0 に初期化します。これは、配列要素の最大合計を格納するために使用されます。

ステップ 2 - x[] および y[] 配列要素の走査を開始します。

ステップ 3 - x[p] の値を一時変数に保存し、nums[] 配列を並べ替えます。

ステップ 4- ループ内でソートされた配列の走査を開始します。

ステップ 5 - 温度が 0 より大きく、nums[q] が y[p] より小さい場合は、nums[q] を y[p] で更新し、温度値を 1 減分します。

ステップ 6

- ループの外側で、更新された配列の走査を開始し、すべての配列要素の合計を取り出し、それを maxSum 変数に格納します。

ステップ 7

- 関数の最後で maxSum を返します。 ＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量

- O(M*NlogN)。O(M) はすべてのクエリの走査に使用され、O(NlogN) は配列の並べ替えに使用されます。

空間複雑度

- 配列をソートする場合、空間複雑度は O(N) です。 方法 2

このアプローチでは、優先キューを使用して、配列要素のペアとその出現時間を保存します。 たとえば、{nums[p], 1} ペアを配列要素ごとに優先キューにプッシュします。同時に、ペア {y[p], x[p]} を優先キューにプッシュします。優先キューでは、ペアは最初の要素に基づいて並べ替えられます。したがって、キューから上位 N 個の要素を取得できます。ここで、ペア {y[p],x[p]} について、y[p] 個の要素を x[p] 回取り出すことができ、合計を最大化するには合計 N 個の要素を取り出す必要があります。

＃＃＃アルゴリズム＃＃＃

ステップ 1 - 「maxSum」を 0 で初期化し、要素のペアとその出現数を保存する優先キューを初期化します。

ステップ 2- すべての配列要素について、{nums[p], 1} ペアをキューに挿入します。

ステップ 3 - 次に、{y[p], x[p]} のペアを優先キューに挿入します。

ステップ 4

- n が 0 より大きくなるまで繰り返します。

ステップ 4.1 - 優先キューから最初の要素を削除します。

ステップ 4.2 - first_ele * max(n, Second_ele) を合計に加算します。ここでは、max(n, Second_ele) を使用して最後のケースを処理します。

ステップ 4.3

- n から Second_ele を減算します。

ステップ 5

- maxSum を返します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(N*logN m*logm)。ここで、O(N) と O(m) は指定された配列の走査に使用され、O(logN) はキュー内の要素の挿入と削除に使用されます。 スペースの複雑さ - キューにペアを格納するための O(N M)。

最初の方法では、最小の x[p] 要素を見つけるために各反復で配列を並べ替える必要があります。プライオリティ キューを使用すると、ヒープ データ構造が使用されるため、要素が挿入または削除されるときに要素を自動的に並べ替えることができます。したがって、コードのパフォーマンスが向上します。

以上が指定された操作を実行した後に可能な配列の合計の最大値の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。