main.cpp (3513B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 // binary string s of length n 13 // can do this any number of times (including zero): 14 // choose an integer 1 <= i <= n and replace s_i with & or | of s_1, s_2, ..., s_i 15 // find minimum number of operations to sort s in ascending order 16 17 // 4 18 // 0011 19 // already sorted, 0 20 21 // 4 22 // 1000 23 // 1 24 // 1001 25 // 1011 26 // 1111 27 // 3 ops 28 29 // idea: for each zero that follows leading ones, they must be flipped one by one. 30 // is the question just how many zeroes follow the first one? 31 // not quite. in cases where there's a one after some zeroes, that one can be flipped 32 // is the answer then min(zeroesAfterFirstOne, onesAfterFirstZero)? 33 34 // stepwise, do we just flip every one until the final sequence of zeroes? 35 36 37 // 5 38 // 01000 39 // 00000 40 41 42 // 8 43 // 01001101 44 // 00001101 45 // 00000101 46 // 00000001 47 // sum = 3 48 49 50 // 7 51 // 0101010 52 // 0001010 53 // 0000010 54 // 0000000 55 56 57 // 7 58 // 0111101 59 // 0111111 60 // steps: 1 61 62 63 // feels like some sort of inequality exists here 64 // is there something about the number of remaining zeroes and ones? 65 // like how many ones are there? If there are more ones then zeroes, only flip zeroes as needed? 66 67 // how many more ones are there after the current positions? 68 // if there are more ones than zeroes, then we skip over the remaining runs of 69 // should we start from the end instead? 70 // if we start from the end: 71 72 // the question here is this: 73 // where do we draw the boundary between ones and zeroes 74 // this position is the spot where there are more 75 // can we compute this incrementally? 76 // like we say what if we drew the line here and then everything on the left must be zeroes and right ones. 77 // this seems to be on the right track, but we also want to remove all leading zeroes. 78 // leading ones can't be flipped so if first position is a one then we just count zeroes 79 80 int countZeroes(string& st) { 81 int res = 0; 82 for(int i = 0; i < st.size(); ++i) { 83 if(st[i] == '0') { 84 res += 1; 85 } 86 } 87 return res; 88 } 89 90 91 int stripLeadingZeroes(string& st) { 92 int leadingZeroes = 0; 93 for(int i = 0; i < st.size(); ++i) { 94 if(st[i] == '1') { 95 leadingZeroes = i; 96 break; 97 } 98 } 99 st = st.substr(leadingZeroes); 100 return leadingZeroes; 101 } 102 103 int main() { 104 105 int testCases, n; 106 string st; 107 cin >> testCases; 108 109 for(int z = 0; z < testCases; ++z) { 110 111 cin >> n; 112 cin >> st; 113 114 // we just count zeroes because everything must become one in such cases. 115 if(st[0] == '1') { 116 cout << countZeroes(st) << endl; 117 continue; 118 } 119 120 int stripped = stripLeadingZeroes(st); 121 122 int trailingZeroes = countZeroes(st); 123 int leadingOnes = 0; 124 125 int best = trailingZeroes; 126 127 for(int i = 0; i < st.size(); ++i) { 128 // what would happen if everyting before, and including the current, index had to be zeroes 129 // and everything after had to be ones? 130 if(st[i] == '1') { 131 leadingOnes += 1; 132 } else { 133 trailingZeroes -= 1; 134 } 135 int currentCost = leadingOnes + trailingZeroes; 136 if(currentCost < best || best == -1) { 137 best = currentCost; 138 } 139 } 140 141 cout << best << endl; 142 143 } 144 }