通过选取二进制字符串中每个"1"左侧的数组元素来最大化和
在本题中，我们将通过选取当前"1"索引左侧未选中的元素来求出数组元素的最大和。
我们可以使用向量列表和 sort() 方法或优先级队列来解决这个问题。优先级队列按排序顺序插入元素。
问题描述- 我们给出了一个长度相同的二进制字符串 alpha 和 arr[]。我们需要逐个选取 alpha 中的所有"1"，并从由 0 到 p 个元素组成的 arr[] 子数组中取出未被选中的最大元素。其中，P 是二进制字符串中已选中"1"的索引。我们需要打印这些数组元素的最大和。
示例
输入
alpha = "01010"; arr[] = {30, 40, 3, 7, 20};
输出
70
解释
对于第一个索引处的"1"，我们可以选择 40。
对于第三个索引处的"1"，我们可以选择 30。
因此，40 加 30 的和为 70。
输入
alpha = "00000"; arr[] = {30, 40, 3, 7, 20};
输出
0
解释- 二进制字符串全为 0。因此，打印总和为 0。
输入
alpha = "00001"; arr[] = {100, 70, 80, 8, 20};
输出
100
解释- 我们选择 100 作为"1"，因为它位于 0 到 4 的子数组中，并且尚未被提取。
方法 1
在此方法中，我们将继续计数 1，并将数组元素推送到列表中。此外，我们继续对列表进行排序，每当我们在二进制字符串中找到"0"时，我们将最后一个元素的 count 个数添加到总和中，并将其从排序后的数组中删除。这里，count 是指最后一个零和当前零之间出现的 1 的数量。
算法
步骤 1- 将"count"和"array_sum"初始化为零，以存储两个 0 之间的 1 的数量以及最大和的输出。
步骤 2 - 另外，定义"numbers"列表来存储数组元素。
步骤 3 - 开始遍历字符串。如果二进制字符串中的当前字符为"1"，则将"count"加 1。
步骤 4 - 否则，使用 while 循环进行迭代，直到"count"不等于 0。在循环中，将最后一个元素添加到"array_sum"，将其从列表中移除，并将"count"减 1。
步骤 5 - 将当前元素推送到列表。
步骤 6 - 使用 sort() 方法对列表进行排序。
步骤 7 - 使用 while 循环进行迭代，直到 count 不等于零。在循环中，将数组的最后一个元素添加到 array_sum，并从列表中移除最后一个元素。
步骤 8 - 返回 array_sum 的值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr, string alpha, int len) {
int count = 0, array_sum = 0;
vector<int> numbers;
// 迭代字符串
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// 从队列中弹出所有 count 个元素
while (count != 0) {
array_sum += numbers[numbers.size() - 1];
numbers.pop_back();
count--;
}
}
// 将元素插入列表
numbers.push_back(arr[p]);
// 对列表进行排序
sort(numbers.begin(), numbers.end());
}
// 如果队列不为空，则弹出元素并计算总和
while (count != 0) {
array_sum += numbers[numbers.size() - 1];
numbers.pop_back();
count--;
}
// 返回答案
return array_sum;
}
int main() {
int len = 5;
string alpha = "01010";
int arr[] = {30, 40, 3, 7, 20};
cout << "根据给定条件，数组元素的最大和为 " << getMaximumSum(arr, alpha, len) << endl;
return 0;
}
输出
根据给定条件，数组元素的最大和为 70
时间复杂度 - O(N*NlogN)，其中遍历字符串复杂度为 O(N)，对数组进行排序复杂度为 O(NlogN)。
空间复杂度 - 将数组元素存储在列表中复杂度为 O(N)。
方法 2
在此方法中，我们将使用优先级队列来保持元素列表的排序。它类似于堆数据结构，并且在堆中插入元素非常高效。
我们可以插入元素，并设置元素在排序顺序中的位置。当我们在二进制字符串中找到"0"时，我们可以从头开始弹出元素。
算法
步骤 1 - 将"count"和"array_sum"初始化为 0。
步骤 2 - 开始遍历二进制字符串。如果当前字符为"1"，则将"count"加 1。
步骤 3 - 如果当前字符为"0"，则使用循环从队列中移除 count 个元素，并将其添加到"array_sum"变量中。
步骤 4 - 将当前元素推送到队列。
步骤 5 - 如果 count 不为零，则从队列中移除 count 个元素。
步骤 6 - 返回"array_sum"值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaximumSum(int *arr, string alpha, int len) {
int count = 0, array_sum = 0;
priority_queue<int> queue;
// 迭代字符串
for (int p = 0; p < len; p++) {
if (alpha[p] == '1') {
count++;
} else {
// 从队列中弹出所有 count 个元素
while (count != 0) {
array_sum += queue.top();
queue.pop();
count--;
}
}
// 将元素插入队列
queue.push(arr[p]);
}
// 如果队列不为空，则弹出元素并计算其和
while (count != 0) {
array_sum += queue.top();
queue.pop();
count--;
}
// 返回答案
return array_sum;
}
int main() {
int len = 5;
string alpha = "01010";
int arr[] = {30, 40, 3, 7, 20};
cout << "根据给定条件，数组元素的最大和为 " << getMaximumSum(arr, alpha, len) << endl;
return 0;
}
输出
根据给定条件，数组元素的最大和为 70
时间复杂度 - O(N*logN)，其中 O(N) 用于遍历字符串，O(logN) 用于将元素插入队列。
空间复杂度 - O(N)，用于将元素存储在队列中。
这里我们使用了列表和队列来解决这个问题。我们可以观察到队列的效率。如果我们需要在每次迭代后对数组进行排序，我们可以使用优先级队列。
