#include <bits/stdc++.h> using namespace std; #define st first #define nd second #define iamspeed ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0) int n, m, len, wir, res, czas; string s; vector<int> K, D; int main() { iamspeed; cin >> m; while(m != 0) { m--; cin >> n >> s; s += '2'; len = wir = res = czas = 0; K.clear(), D.clear(); for(int i = 0 ; i < s.size() ; i++) { if(s[i] == '0') len++; else if(s[i] == '1') { wir++; if(i > 0 && s[i - 1] == '0') { if(K.empty() && s[0] != '1') K.push_back(len); else D.push_back(len); } len = 0; } else if(s[i] == '2' && s[i - 1] == '0') { K.push_back(len); } } if(!wir) { cout << 0 << endl; continue; } sort(K.begin(), K.end()); sort(D.begin(), D.end()); while(!K.empty() || !D.empty()) { if(!D.empty() && D.back() - (2 * czas) < 1) D.clear(); if(!K.empty() && K.back() - czas < 1) K.clear(); if(!K.empty() && !D.empty()) { if(D.back() - (2 * czas) > (K.back() - czas) * 2) { if(D.back() - (2 * czas) > 1) res += D.back() - 1 - (2 * czas); else res += 1; if(D.back() <= 2) czas--; czas += 2; D.pop_back(); } else { res += K.back() - czas; K.pop_back(); czas += 1; } } else if(!K.empty()) { res += K.back() - czas; K.pop_back(); czas += 1; } else if(!D.empty()) { if(D.back() - (2 * czas) > 1) res += D.back() - 1 - (2 * czas); else res += 1; if(D.back() <= 2) czas--; czas += 2; D.pop_back(); } } cout << n - res << endl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | #include <bits/stdc++.h> using namespace std; #define st first #define nd second #define iamspeed ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0) int n, m, len, wir, res, czas; string s; vector<int> K, D; int main() { iamspeed; cin >> m; while(m != 0) { m--; cin >> n >> s; s += '2'; len = wir = res = czas = 0; K.clear(), D.clear(); for(int i = 0 ; i < s.size() ; i++) { if(s[i] == '0') len++; else if(s[i] == '1') { wir++; if(i > 0 && s[i - 1] == '0') { if(K.empty() && s[0] != '1') K.push_back(len); else D.push_back(len); } len = 0; } else if(s[i] == '2' && s[i - 1] == '0') { K.push_back(len); } } if(!wir) { cout << 0 << endl; continue; } sort(K.begin(), K.end()); sort(D.begin(), D.end()); while(!K.empty() || !D.empty()) { if(!D.empty() && D.back() - (2 * czas) < 1) D.clear(); if(!K.empty() && K.back() - czas < 1) K.clear(); if(!K.empty() && !D.empty()) { if(D.back() - (2 * czas) > (K.back() - czas) * 2) { if(D.back() - (2 * czas) > 1) res += D.back() - 1 - (2 * czas); else res += 1; if(D.back() <= 2) czas--; czas += 2; D.pop_back(); } else { res += K.back() - czas; K.pop_back(); czas += 1; } } else if(!K.empty()) { res += K.back() - czas; K.pop_back(); czas += 1; } else if(!D.empty()) { if(D.back() - (2 * czas) > 1) res += D.back() - 1 - (2 * czas); else res += 1; if(D.back() <= 2) czas--; czas += 2; D.pop_back(); } } cout << n - res << endl; } } |