极客笔记C++ 执行给定操作后的最大可能数组和
在这个问题中，我们将对数组元素执行给定的操作，并找到最后的最大和。
在每个操作中，我们可以从数组中选择最多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个元素，但我们只有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
解释 - 在这里，我们可以在每个操作中替换最多x[p]个元素。在最后一个操作中，我们可以用100替换数组的每个元素，这样可以得到最大和为100。
方法1
在这个方法中，我们将遍历x[]和y[]数组。在每次迭代中，我们将对数组进行排序，以获得最多x[p]个小于y[p]元素的数组元素，并用y[p]替换它们。
步骤
步骤1 - 将’maxSum’初始化为0，用于存储数组元素的最大和。
步骤2 - 开始遍历x[]和y[]数组元素。
步骤3 - 将x[p]的值放入临时变量中，并对nums[]数组进行排序。
步骤4 - 在循环内部开始遍历排序后的数组。
步骤5 - 如果temp大于0且nums[q]小于y[p]，则将nums[q]更新为y[p]，并将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]}对，我们可以取出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)加到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]元素。使用优先队列在插入或删除元素时自动对元素进行排序，因为它使用了堆数据结构。因此，它提高了代码的性能。