將二進位制字串的所有字元轉換為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)。