#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; typedef long long int LL; typedef vector<LL> VL; typedef vector<VL> VVL; #define FOR(x, b, e) for(int x = b; x < (e); ++x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define EACH(x, y) for(auto &(x) : y) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define PB push_back struct City { LL start; LL end; LL duration; bool oneWay = false; bool operator< (const City& other) const { if(duration != other.duration) return duration > other.duration; else return oneWay > other.oneWay; } }; // firstly get all the intervals, sorted in descending order, get the biggest ones, make borders with vaccinated cities // do as long as there are any left, check how many are unvaccinated, this is the result int solve(string &s) { vector<City> vc; LL len = 0; City city; REP(i, SIZE(s)) { if (s[i] == '0') { if (!len) { city.start = i; if (i == 0) city.oneWay = true; } len++; } if (s[i] == '1' || i + 1 == SIZE(s)) { if (len) { i + 1 == SIZE(s) ? city.end = i : city.end = i - 1; city.duration = len; if (i + 1 == SIZE(s)) city.oneWay = true; vc.PB(city); city.start = 0; city.end = 0; city.duration = 0; city.oneWay = false; } len = 0; } } sort(ALL(vc)); LL healthy = 0, dayPenalty = 0; EACH(item, vc) { if ((item.oneWay ? item.duration - (dayPenalty / 2) : item.duration - dayPenalty - 1) <= 0) break; if (item.oneWay) healthy += item.duration - (dayPenalty / 2); else healthy += item.duration - dayPenalty - 1; dayPenalty += 2; } return SIZE(s) - healthy; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, t; cin >> t; REP(i, t) { cin >> n; string s; VL vec; cin >> s; LL ans = solve(s); cout << ans << '\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 101 | #include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; typedef long long int LL; typedef vector<LL> VL; typedef vector<VL> VVL; #define FOR(x, b, e) for(int x = b; x < (e); ++x) #define REP(x, n) for(int x = 0; x < (n); ++x) #define EACH(x, y) for(auto &(x) : y) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int)(x).size()) #define PB push_back struct City { LL start; LL end; LL duration; bool oneWay = false; bool operator< (const City& other) const { if(duration != other.duration) return duration > other.duration; else return oneWay > other.oneWay; } }; // firstly get all the intervals, sorted in descending order, get the biggest ones, make borders with vaccinated cities // do as long as there are any left, check how many are unvaccinated, this is the result int solve(string &s) { vector<City> vc; LL len = 0; City city; REP(i, SIZE(s)) { if (s[i] == '0') { if (!len) { city.start = i; if (i == 0) city.oneWay = true; } len++; } if (s[i] == '1' || i + 1 == SIZE(s)) { if (len) { i + 1 == SIZE(s) ? city.end = i : city.end = i - 1; city.duration = len; if (i + 1 == SIZE(s)) city.oneWay = true; vc.PB(city); city.start = 0; city.end = 0; city.duration = 0; city.oneWay = false; } len = 0; } } sort(ALL(vc)); LL healthy = 0, dayPenalty = 0; EACH(item, vc) { if ((item.oneWay ? item.duration - (dayPenalty / 2) : item.duration - dayPenalty - 1) <= 0) break; if (item.oneWay) healthy += item.duration - (dayPenalty / 2); else healthy += item.duration - dayPenalty - 1; dayPenalty += 2; } return SIZE(s) - healthy; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, t; cin >> t; REP(i, t) { cin >> n; string s; VL vec; cin >> s; LL ans = solve(s); cout << ans << '\n'; } return 0; } |