数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
