資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究執行給定操作後陣列的最大可能和
在這個問題中，我們將對陣列元素執行給定的操作，最後找到最大和。
這裡，在每次操作中，我們最多可以選擇陣列中的 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
解釋 − 讓我們逐一執行每個操作。
在第一次操作中，我們將用 500 替換 7 個元素。因此，陣列變為 {10, 8, 500, 60, 20, 18, 30, 60}。
在第二次操作中，我們可以用 10 替換最多 2 個元素，但我們只有一個小於 10 的元素。因此，我們將用 10 替換 8，陣列變為 {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
解釋 − 這裡，我們可以在每次操作中最多替換 x[p] 個元素。在最後一次操作中，我們可以用 100 替換陣列的每個元素，並且我們可以獲得等於 100 的最大和。
方法 1
在這種方法中，我們將遍歷 x[] 和 y[] 陣列。在每次迭代中，我們將對陣列進行排序以獲得最多 x[p] 個最小的且小於 y[p] 元素的陣列元素，並用 y[p] 替換它們。
演算法
步驟 1 − 用 0 初始化 'maxSum' 以儲存陣列元素的最大和。
步驟 2 − 開始遍歷 x[] 和 y[] 陣列元素。
步驟 3 − 將 x[p] 值放入 temp 變數並對 nums[] 陣列進行排序。
步驟 4 − 在迴圈內開始遍歷排序後的陣列。
步驟 5 − 如果 temp 大於 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) 用於對陣列進行排序。
方法 2
在這種方法中，我們將使用優先佇列來儲存陣列元素及其出現次數的對。
例如，對於每個陣列元素，我們將 {nums[p], 1} 對推入優先佇列。此外，我們還將 {y[p], x[p]} 對推入優先佇列。在優先佇列中，對將根據第一個元素進行排序。因此，我們可以從佇列中獲取最高的 N 個元素。這裡，對於 {y[p], x[p]} 對，我們可以獲取 x[p] 次 y[p] 元素，我們需要獲取總共 N 個元素以最大化總和。
演算法
步驟 1 − 用 0 初始化 'maxSum' 和優先佇列以儲存元素及其出現次數的對。
步驟 2 − 對於所有陣列元素，將 {nums[p], 1} 對插入佇列。
步驟 3 − 之後，將 {y[p], x[p]} 對插入優先佇列。
步驟 4 − 進行迭代，直到 n 大於 0。
步驟 4.1 − 從優先佇列中獲取第一個元素。
步驟 4.2 − 將 first_ele * max(n, second_ele) 新增到 sum 中。這裡，我們使用 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] 個元素。使用優先佇列會在我們向其中插入或刪除元素時自動對元素進行排序，因為它使用堆資料結構。因此，它提高了程式碼的效能。
457 次檢視
