#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct row { int leng; int sids; }; vector<struct row> A; bool comp(struct row a, struct row b) { return a.leng*2/a.sids > b.leng*2/b.sids; } int main() { int q; scanf("%d", &q); for (int i=0;i<q;i++) { A.clear(); int n; scanf("%d", &n); char c; int sds = 1; int leng = 0; for (int j=0;j<n;j++) { scanf(" %c", &c); if (c == '1') { if (leng > 0) { A.push_back(row{leng,sds}); } sds = 2; leng = 0; } else leng++; } if (leng > 0) A.push_back(row{leng,1}); sort(A.begin(), A.end(), comp); int tp = 0; int k, s = 0; for (int i=0;i<A.size();i++) { if (A[i].sids == 1) { k = A[i].leng-tp; if (k <= 0) break; s += k; tp++; } else { k = A[i].leng-2*tp; if (k <= 0) break; if (k == 1) s++; else s += k-1; tp += 2; } } printf("%d\n", n-s); } }
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; struct row { int leng; int sids; }; vector<struct row> A; bool comp(struct row a, struct row b) { return a.leng*2/a.sids > b.leng*2/b.sids; } int main() { int q; scanf("%d", &q); for (int i=0;i<q;i++) { A.clear(); int n; scanf("%d", &n); char c; int sds = 1; int leng = 0; for (int j=0;j<n;j++) { scanf(" %c", &c); if (c == '1') { if (leng > 0) { A.push_back(row{leng,sds}); } sds = 2; leng = 0; } else leng++; } if (leng > 0) A.push_back(row{leng,1}); sort(A.begin(), A.end(), comp); int tp = 0; int k, s = 0; for (int i=0;i<A.size();i++) { if (A[i].sids == 1) { k = A[i].leng-tp; if (k <= 0) break; s += k; tp++; } else { k = A[i].leng-2*tp; if (k <= 0) break; if (k == 1) s++; else s += k-1; tp += 2; } } printf("%d\n", n-s); } } |