#include <bits/stdc++.h> struct comparator { bool operator()(std::pair <int, int> const& a, std::pair <int, int> const& b) const { if (a.first - a.second == b.first - b.second) return a.second > b.second; else return a.first - a.second < b.first - b.second; } }; int32_t main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int tests_number; std::cin >> tests_number; while (tests_number--) { int cities_number; std::cin >> cities_number; std::string cities; std::cin >> cities; bool ok = true; for (auto i : cities) if (i == '1') ok = false; if (ok) std::cout << "0\n"; else { std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int>>, comparator> intervals; size_t start = 0, end = cities.size(); for (size_t i = 0; i < cities.size(); ++i) { if (cities[i] == '1') { if (i > 0) { intervals.push(std::make_pair(i, 1)); } start = i; break; } } for (int i = cities.size() - 1; i >= 0; --i) { if (cities[i] == '1') { if (i < (int)cities.size() - 1) { intervals.push(std::make_pair(cities.size() - i - 1, 1)); } end = i + 1; break; } } int healthy = 0; for (size_t i = start; i < end; ++i) { if (cities[i] == '1') { if (healthy > 0) { intervals.push(std::make_pair(healthy, 2)); } healthy = 0; } else ++healthy; } int result = 0; for (auto i : cities) if (i == '1') ++result; while (true) { if (intervals.size() == 0) break; auto x = intervals.top(); intervals.pop(); x.first -= 1; x.second -= 1; if (x.second > 0) { intervals.push(x); } std::vector <std::pair <int, int>> tmp; while (!intervals.empty()) { auto x = intervals.top(); intervals.pop(); result += std::min(x.first, x.second); x.first -= x.second; if (x.first > 0) tmp.push_back(x); } for (auto i : tmp) intervals.push(i); } std::cout << result << '\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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include <bits/stdc++.h> struct comparator { bool operator()(std::pair <int, int> const& a, std::pair <int, int> const& b) const { if (a.first - a.second == b.first - b.second) return a.second > b.second; else return a.first - a.second < b.first - b.second; } }; int32_t main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int tests_number; std::cin >> tests_number; while (tests_number--) { int cities_number; std::cin >> cities_number; std::string cities; std::cin >> cities; bool ok = true; for (auto i : cities) if (i == '1') ok = false; if (ok) std::cout << "0\n"; else { std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int>>, comparator> intervals; size_t start = 0, end = cities.size(); for (size_t i = 0; i < cities.size(); ++i) { if (cities[i] == '1') { if (i > 0) { intervals.push(std::make_pair(i, 1)); } start = i; break; } } for (int i = cities.size() - 1; i >= 0; --i) { if (cities[i] == '1') { if (i < (int)cities.size() - 1) { intervals.push(std::make_pair(cities.size() - i - 1, 1)); } end = i + 1; break; } } int healthy = 0; for (size_t i = start; i < end; ++i) { if (cities[i] == '1') { if (healthy > 0) { intervals.push(std::make_pair(healthy, 2)); } healthy = 0; } else ++healthy; } int result = 0; for (auto i : cities) if (i == '1') ++result; while (true) { if (intervals.size() == 0) break; auto x = intervals.top(); intervals.pop(); x.first -= 1; x.second -= 1; if (x.second > 0) { intervals.push(x); } std::vector <std::pair <int, int>> tmp; while (!intervals.empty()) { auto x = intervals.top(); intervals.pop(); result += std::min(x.first, x.second); x.first -= x.second; if (x.first > 0) tmp.push_back(x); } for (auto i : tmp) intervals.push(i); } std::cout << result << '\n'; } } return 0; } |