将二进制字符串的所有字符转换为0的最小成本

---

二进制字符串是指仅包含二进制数字的字符串。在这个问题中，我们给定一个二进制字符串，一个数组表示从第 i 个索引开始可以翻转 1 的最后一个索引，每个索引的成本由另一个成本数组给出。我们必须对字符串执行一些操作才能使字符串完全变为零。

示例

让我们通过一个例子来理解这个问题：

输入

string str = "101011"
int arr[] = {1, 2, 2, 4, 5, 5};
int cost[] = {3, 9, 2, 3, 7, 2}

输出

19

解释

这里我们必须翻转第一位，所以成本为 3，下一个 0 也将被翻转，然后我们必须翻转它，成本为 3 + 9，即 12。再次下一个 1 只翻转 1 次，所以不需要翻转它。下一个零在这里没有翻转，所以也不需要翻转它。

然后我们需要翻转倒数第二个 1，它还将翻转下一个 1，总成本为 7，总成本为 19。

方法 1

在这种方法中，我们将使用优先队列来指示我们必须找到翻转影响的索引范围。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get the required cost
int costReq(string s, int size, int arr[], int cost[]){
   // store the elements in the priority queue all the elements will be stored in the smallest first side 
   priority_queue<int, vector<int>, greater<int>> pq;

   // variable to store the number of times the string is flipped 
   int countFlips = 0;
   // variable to store the required minimum cost or to store the answer
   int ans = 0;
   // using for loop traversing over the string 
   for(int i = 0; i < size; i++){		
      // remove all the values from the priority queue which have value less than current index 
      while(pq.empty() == false && pq.top() < i){
         // poping the elements 
         pq.pop(); 
         countFlips--; // reducing the count of the flips 
      }        
      // updating the value of the current character based on the number of times it have been flipped
      if(countFlips & 1){
         // if the count of the flips is odd then change the current index 
         if(s[i] == '1'){
            s[i] = '0';
         } else {
            s[i] = '1';
         }
      }
      // after updation if the current index is non-zero then we need to flip it 
      if (s[i] == '1'){
         // update the count of the flips 
         countFlips++;
         // add number of index upto which we are flipping 
         pq.push(arr[i]);			
         // add cost to answer 
         ans += cost[i];
      }
   }
   return ans; // return the final answer 
}
int main(){
   string str = "101011"; // given string 
   int arr[] = {1, 2, 2, 4, 5, 5}; // given index array
   int cost[] = {3, 9, 2, 3, 7, 2}; // given cost array 
   int n = str.length(); // getting length of the string 
   // calling to the function to get the answer 
   cout << "The minimum cost required to flip all the ones to zeros is: "<<costReq(str, n, arr, cost)<<endl;
   return 0;
}

输出

The minimum cost required to flip all the ones to zeros is: 19

时间和空间复杂度

上述代码的时间复杂度为 O(N*log(N))，其中 N 是给定字符串的大小，由于优先队列，我们得到对数因子。

上述代码的空间复杂度为 O(N)，因为我们使用额外的空间作为优先队列。

方法 2

在这种方法中，我们将使用差分数组来实现代码。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get the required cost
int costReq(string s, int size, int arr[], int cost[]){
   // vector to work as the difference array 
   vector<int> diff_arr(size + 1); 
   // variable to store the number of times the string is flipped 
   int countFlips = 0;
   // variable to store the required minimum cost or to store the answer
   int ans = 0;
   // using for loop traversing over the string 
   for(int i = 0; i < size; i++){        
      // updating the value of the flips using the differ rence array 
      countFlips += diff_arr[i];        
      // updating the value of the current character based on the number of times it has been flipped
      if(countFlips & 1){
         // if the count of the flips is odd then change the current index 
         if(s[i] == '1'){
            s[i] = '0';
         } else {
            s[i] = '1';
         }
      }
      // after updation if the current index is non-zero then we need to flip it 
      if (s[i] == '1'){
         // update the count of the flips 
         countFlips++;
         // update the value of the difference array on the next index of the ending 
         diff_arr[arr[i] + 1]--;
         // add cost to answer 
         ans += cost[i];
      }
   }
   return ans; // return the final answer 
}
int main(){
   string str = "101011"; // given string 
   int arr[] = {1, 2, 2, 4, 5, 5}; // given index array
   int cost[] = {3, 9, 2, 3, 7, 2}; // given cost array 
   int n = str.length(); // getting lenth of the string 
   // calling to the function to get the answer 
   cout << "The minimum cost required to flip all the ones to zeros is: "<<costReq(str, n, arr, cost)<<endl;
   return 0;
}

输出

The minimum cost required to flip all the ones to zeros is: 19

时间和空间复杂度

上述代码的时间复杂度为 O(N)，因为我们只是遍历字符串并维护一个数组。

上述代码的空间复杂度为 O(N)，因为我们维护差分数组。

结论

在本教程中，我们实现了一个程序来查找将给定的二进制字符串完全转换为零的最小成本。我们给定一个数组，其中每个索引表示如果我们翻转该索引，则会翻转多少个向前元素，并且还给出了成本。我们实现了两种方法，一种使用优先队列，时间复杂度为 O(N*log(N))，另一种使用差分数组，时间复杂度为 O(N)。