#include<cstdio> #include<algorithm> #include<vector> using namespace std; #define MAXN 100000 #undef DEBUGM void przypadek(){ int n, wyn=0, dlprzed=0, zostalo; char c; int t=0; scanf("%d ", &n); vector<pair<int, int>> v; for (int i = 0; i < n; ++i) { scanf("%c", &c); if (c == '0') { dlprzed += 1; } else if (c == '1') { if (dlprzed > 0) { int boki = wyn==0?1:2; v.push_back(make_pair(2/boki * dlprzed, boki)); dlprzed = 0; } wyn += 1; } } if (dlprzed > 0) { v.push_back(make_pair(2 * dlprzed, 1)); dlprzed = 0; } zostalo = v.size(); sort(v.begin(), v.end()); while (zostalo > 0) { --zostalo; int boki = v[zostalo].second; int dl = v[zostalo].first * boki /2; int potstrata = t*boki; wyn += min(potstrata, dl); int nowadl = dl - potstrata; if (nowadl > 0) { if (boki == 2 && nowadl > 1) { wyn += 1; if (nowadl > 2) t++; }//else 1 -> nothing t++; } } printf("%d\n", wyn); } int main(){ int t; scanf("%d ", &t); for (int k = 0; k < t; ++k) { przypadek(); } }
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 | #include<cstdio> #include<algorithm> #include<vector> using namespace std; #define MAXN 100000 #undef DEBUGM void przypadek(){ int n, wyn=0, dlprzed=0, zostalo; char c; int t=0; scanf("%d ", &n); vector<pair<int, int>> v; for (int i = 0; i < n; ++i) { scanf("%c", &c); if (c == '0') { dlprzed += 1; } else if (c == '1') { if (dlprzed > 0) { int boki = wyn==0?1:2; v.push_back(make_pair(2/boki * dlprzed, boki)); dlprzed = 0; } wyn += 1; } } if (dlprzed > 0) { v.push_back(make_pair(2 * dlprzed, 1)); dlprzed = 0; } zostalo = v.size(); sort(v.begin(), v.end()); while (zostalo > 0) { --zostalo; int boki = v[zostalo].second; int dl = v[zostalo].first * boki /2; int potstrata = t*boki; wyn += min(potstrata, dl); int nowadl = dl - potstrata; if (nowadl > 0) { if (boki == 2 && nowadl > 1) { wyn += 1; if (nowadl > 2) t++; }//else 1 -> nothing t++; } } printf("%d\n", wyn); } int main(){ int t; scanf("%d ", &t); for (int k = 0; k < t; ++k) { przypadek(); } } |