执行给定操作后的最大可能数组和

在这个问题中，我们将对数组元素执行给定的操作，并找到最后的最大和。

在这里，每次操作中，我们可以从数组中最多选择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，用于存储数组元素的最大和。

歌者PPT

歌者PPT，AI 写 PPT 永久免费

下载

步骤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)，用于将对存储到队列中。