#include <iostream> #include <string> #include <algorithm> #include <queue> using namespace std; int main() { int t; cin >> t; for (int test_case = 0; test_case < t; ++test_case) { int n; string sick; cin >> n >> sick; priority_queue<int> healthy_lengths; int current_length = 0; int left = -1, right; for (char bit : sick) { if (bit == '1') { if (left < 0) { left = current_length; } else { healthy_lengths.push(current_length); } current_length = 0; } else { current_length++; } } right = current_length; left = max(0, left); int vaccinated_cities = 0; int days = 0; while (!healthy_lengths.empty() && healthy_lengths.top() - 2 * days > 3) { int length = healthy_lengths.top(); healthy_lengths.pop(); if (length - 2 * days == 1 || length - 2 * days == 2) { vaccinated_cities++; days++; } else if (length - 2 * days - 1 > 0) { vaccinated_cities += length - 2 * days - 1; days += 2; } } if (left - days > 0) { vaccinated_cities += left - days; days++; } if (right - days > 0) { vaccinated_cities += right - days; days++; } int length = healthy_lengths.top(); healthy_lengths.pop(); if (length - 2 * days == 1 || length - 2 * days == 2) { vaccinated_cities++; days++; } cout << n - vaccinated_cities << '\n'; } return 0; }
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 | #include <iostream> #include <string> #include <algorithm> #include <queue> using namespace std; int main() { int t; cin >> t; for (int test_case = 0; test_case < t; ++test_case) { int n; string sick; cin >> n >> sick; priority_queue<int> healthy_lengths; int current_length = 0; int left = -1, right; for (char bit : sick) { if (bit == '1') { if (left < 0) { left = current_length; } else { healthy_lengths.push(current_length); } current_length = 0; } else { current_length++; } } right = current_length; left = max(0, left); int vaccinated_cities = 0; int days = 0; while (!healthy_lengths.empty() && healthy_lengths.top() - 2 * days > 3) { int length = healthy_lengths.top(); healthy_lengths.pop(); if (length - 2 * days == 1 || length - 2 * days == 2) { vaccinated_cities++; days++; } else if (length - 2 * days - 1 > 0) { vaccinated_cities += length - 2 * days - 1; days += 2; } } if (left - days > 0) { vaccinated_cities += left - days; days++; } if (right - days > 0) { vaccinated_cities += right - days; days++; } int length = healthy_lengths.top(); healthy_lengths.pop(); if (length - 2 * days == 1 || length - 2 * days == 2) { vaccinated_cities++; days++; } cout << n - vaccinated_cities << '\n'; } return 0; } |