#include <iostream> #include <string> #include <vector> #include <algorithm> int pom(int index, const std::vector<int> &bi_intervals, int days_passed) { int counter = 0; while (index < bi_intervals.size()) { if (bi_intervals[index] - 2 * days_passed > 2) { counter += bi_intervals[index] - 2 * days_passed - 1; days_passed += 2; ++index; } else { break; } } if (bi_intervals[index] - 2 * days_passed > 0) { ++counter; } return counter; } int solution() { int n; std::cin >> n; std::string input; std::cin >> input; std::vector<int> uni_intervals; std::vector<int> bi_intervals; int begin = 0; for (int i = 1; i < n; ++i) { if (input[i] != input[i - 1]) { if (input[i - 1] == '0') { if (begin == 0) { uni_intervals.push_back(i - begin); } else { bi_intervals.push_back(i - begin); } } begin = i; } } if (input[n - 1] == '0') { uni_intervals.push_back(n - begin); } if (uni_intervals.size() == 1 && uni_intervals[0] == n) { return 0; } std::sort(uni_intervals.begin(), uni_intervals.end(), std::greater<int>()); std::sort(bi_intervals.begin(), bi_intervals.end(), std::greater<int>()); // bez alf int counter = pom(0, bi_intervals, 0); if (uni_intervals.empty()) { return n - counter; } // jedna alfa int counter2 = pom(0, bi_intervals, 1) + uni_intervals[0]; if (counter2 > counter) { counter = counter2; } if (uni_intervals.size() < 2) { return n - counter; } // dwie alfy counter2 = pom(0, bi_intervals, 2) + uni_intervals[0] + uni_intervals[1] - 1; if (counter2 > counter) { counter = counter2; } return n - counter; } int main() { int t; std::cin >> t; while (t--) { std::cout << solution() << "\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 | #include <iostream> #include <string> #include <vector> #include <algorithm> int pom(int index, const std::vector<int> &bi_intervals, int days_passed) { int counter = 0; while (index < bi_intervals.size()) { if (bi_intervals[index] - 2 * days_passed > 2) { counter += bi_intervals[index] - 2 * days_passed - 1; days_passed += 2; ++index; } else { break; } } if (bi_intervals[index] - 2 * days_passed > 0) { ++counter; } return counter; } int solution() { int n; std::cin >> n; std::string input; std::cin >> input; std::vector<int> uni_intervals; std::vector<int> bi_intervals; int begin = 0; for (int i = 1; i < n; ++i) { if (input[i] != input[i - 1]) { if (input[i - 1] == '0') { if (begin == 0) { uni_intervals.push_back(i - begin); } else { bi_intervals.push_back(i - begin); } } begin = i; } } if (input[n - 1] == '0') { uni_intervals.push_back(n - begin); } if (uni_intervals.size() == 1 && uni_intervals[0] == n) { return 0; } std::sort(uni_intervals.begin(), uni_intervals.end(), std::greater<int>()); std::sort(bi_intervals.begin(), bi_intervals.end(), std::greater<int>()); // bez alf int counter = pom(0, bi_intervals, 0); if (uni_intervals.empty()) { return n - counter; } // jedna alfa int counter2 = pom(0, bi_intervals, 1) + uni_intervals[0]; if (counter2 > counter) { counter = counter2; } if (uni_intervals.size() < 2) { return n - counter; } // dwie alfy counter2 = pom(0, bi_intervals, 2) + uni_intervals[0] + uni_intervals[1] - 1; if (counter2 > counter) { counter = counter2; } return n - counter; } int main() { int t; std::cin >> t; while (t--) { std::cout << solution() << "\n"; } return 0; } |