main.cpp (1302B)
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 // n seats 11 // no sitting next to each other 12 // binary string for occupancy 13 14 // Your task is to calculate the minimum total number of students seated when it is impossible to seat anyone else in the row 15 16 17 using namespace std; 18 19 int main() { 20 21 int testCases; 22 cin >> testCases; 23 24 for(int z = 0; z < testCases; ++z) { 25 int n; 26 string current; 27 cin >> n; 28 cin >> current; 29 30 ll sum = 0; 31 for(int i = 0; i < current.size(); ++i) { 32 if(current[i] == '1') 33 sum += 1; 34 } 35 36 37 for(int i = 0; i < current.size(); ++i) { 38 if(current[i] == '1') { 39 continue; 40 } 41 if(i > 0 && current[i-1] == '1') { 42 continue; 43 } 44 if(i + 1 < current.size() && current[i+1] == '1') { 45 continue; 46 } 47 if(i + 1 < current.size() && !(i + 2 < current.size() && current[i+2] == '1')) { 48 current[i+1] = '1'; 49 } 50 else { 51 current[i] = '1'; 52 } 53 sum += 1; 54 } 55 56 cout << sum << endl; 57 } 58 }