在這個問題中，我們將對陣列元素執行給定的操作，並找到最後的最大和。
在這裡，每次操作中，我們可以從陣列中最多選擇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中文網其他相關文章！
