執行給定操作後的最大可能數組和

在這個問題中，我們將對陣列元素執行給定的操作，並找到最後的最大和。

在這裡，每次操作中，我們可以從陣列中最多選擇X[p]個元素，並用Y[p]個元素替換它們，以最大化總和。

在簡單的方法中，我們將找到X[p]陣列元素，這些元素小於Y[p]元素，並將其替換為Y[p]。

在高效的方法中，我們將使用優先隊列來獲得最大的總和。

問題陳述− 我們給定了包含N個數字的nums[]陣列。同時，我們給定了包含M個整數的X[]和Y[]陣列。我們需要對nums[]陣列執行以下操作。

• 我們需要對X[]和Y[]元素的每個元素執行M次操作。在每次操作中，我們需要從陣列nums[]中選擇最大的X[p]元素，並將其替換為Y[p]。

給定的任務是在執行M次操作後找到nums[]陣列元素的最大和。

範例範例

輸入

nums[] = {10, 8, 7, 60, 20, 18, 30, 60}; m = 3; x[] = {1, 2, 5}; y[] = {500, 10, 2};

輸出

708

Explanation − 讓我們逐一執行每個動作。

• 在第一次操作中，我們將用500取代7個元素。所以，陣列變成 {10, 8, 500, 60, 20, 18, 30, 60}。

• 在第二次操作中，我們最多可以用10替換2個元素，但我們只有1個小於10的元素。所以，我們將8替換為10，陣列變成{10, 10, 500, 60, 20, 18, 30, 60}。

• 在第三個運算中，我們最多可以用2取代5個元素，但陣列中沒有任何小於2的元素。因此，我們不會替換任何元素。

輸入

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 3, 6}; y[] = {10, 8, 21};

輸出

230

解釋 − y[]陣列的所有元素都小於原始數組的元素。因此，我們不需要替換給定數組的任何元素來獲得最大的和。

輸入

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 4, 5}; y[] = {50, 60, 100};

輸出

500

Explanation − 在這裡，我們可以在每次運算中最多替換x[p]個元素。在最後一次操作中，我們可以將數組中的每個元素替換為100，從而得到最大和等於100。

方法一

在這個方法中，我們將遍歷x[]和y[]陣列。在每次迭代中，我們將對數組進行排序，以獲取最多x[p]個小於y[p]元素的數組元素，並用y[p]替換它們。

演算法

步驟 1 − 將‘maxSum’初始化為0，用於儲存陣列元素的最大和。

步驟2 − 開始遍歷x[]和y[]陣列元素。

步驟 3 − 將 x[p] 的值存入臨時變量，並對 nums[] 數組進行排序。

第四步− 在迴圈內開始遍歷已排序的陣列。

步驟 5 − 如果溫度大於0，且 nums[q] 小於 y[p]，則使用 y[p] 更新 nums[q]，並將 temp 值減1。

步驟6− 在循環之外，開始遍歷更新後的數組，將所有數組元素的和取出並儲存到maxSum變數中。

第7步 − 在函數結束時傳回maxSum。

範例

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int q, int x[], int y[]) {
    int maxSum = 0;
    // Traverse X[] and Y[] array
    for (int p = 0; p < q; p++) {
        // Replacing x[p] number of elements of nums[] array with y[p] if they are lesser than y[p]
        int temp = x[p];
        sort(nums, nums + n);
        for (int q = 0; q < n; q++) {
            if (temp > 0 && nums[q] < y[p]) {
                nums[q] = y[p];
                temp--;
            }
        }
    }
    // Sum of the array
    for (int p = 0; p < n; p++) {
        maxSum += nums[p];
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

輸出

The maximum sum we can get by replacing the array values is 708

時間複雜度− O(M*NlogN)，其中O(M)用於遍歷所有查詢，O(NlogN)用於對陣列進行排序。

空間複雜度− 對於陣列進行排序，空間複雜度為O(N)。

方法二

在這種方法中，我們將使用優先佇列來儲存陣列元素和其出現次數的配對。

例如，我們將為每個陣列元素將{nums[p]，1}對推入優先隊列。同時，我們將{y[p]，x[p]}對推入優先隊列。在優先隊列中，對將根據第一個元素進行排序。因此，我們可以從隊列中取出最高的N個元素。在這裡，對於{y[p]，x[p]}對，我們可以取出y[p]元素x[p]次，並且我們需要取出總共N個元素以最大化總和。

演算法

Step 1 − Initialize the ‘maxSum’ with 0 and the priority queue to store the pair of elements and their number of occurrences.

第二步驟− 對於所有的陣列元素，將{nums[p], 1}對插入佇列中。

步驟 3 − 然後，將 {y[p], x[p]} 對插入優先隊列中。

第四步− 迭代直到 n 大於 0。

步驟 4.1 − 從優先佇列中取出第一個元素。

步驟 4.2 − 將 first_ele * max(n, second_ele) 加到總和中。這裡，我們使用 max(n, second_ele) 來處理最後一種情況。

步驟 4.3 − 從 n 中減去 second_ele。

步驟5− 回傳maxSum。

範例

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int m, int x[], int y[]) {
    int maxSum = 0, p;
    // To get maximum sum
    priority_queue<pair<int, int>> p_que;
    // Insert nums[] array pairs into the queue
    for (p = 0; p < n; p++)
        p_que.push({nums[p], 1});
    // Push replacement pairs
    for (p = 0; p < m; p++)
        p_que.push({y[p], x[p]});
    // Add the first N elements of the priority queue in the sum
    while (n > 0) {
        // Get top element of priority queue
        auto temp = p_que.top();
        // Remove top element
        p_que.pop();
        // Add value to the sum
        maxSum += temp.first * min(n, temp.second);
        // Change N
        n -= temp.second;
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

輸出

The maximum sum we can get by replacing the array values is 708

時間複雜度 - O(N*logN m*logm)，其中O(N)和O(m)用於遍歷給定的數組，O(logN)用於插入和刪除佇列中的元素。

空間複雜度 - O(N M)，用於將對儲存到佇列。

在第一種方法中，我們需要在每次迭代中對陣列進行排序，以找到最小的x[p]個元素。使用優先佇列在插入或刪除元素時自動對元素進行排序，因為它使用了堆疊資料結構。因此，它可以提高程式碼的效能。

以上是執行給定操作後的最大可能數組和的詳細內容。更多資訊請關注PHP中文網其他相關文章！