#include <bits/stdc++.h> using namespace std; priority_queue<tuple<int,int,int>> Q; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int test,n,wyn,i,dl,il; bool xd; char a; cin >> test; while(test--) { wyn=0; while(Q.size()) Q.pop(); cin >> n; for(i=1, dl=0, xd=1; i<=n; i++) { cin >> a; if(a=='1') { wyn++; if(dl>0) { Q.push({dl/(xd ? 1 : 2), dl, (xd ? 1 : 2)}); } xd=0; dl=0; } else dl++; } if(dl>0) { Q.push({dl, dl, 1}); } il=0; while(Q.size()) { tuple<int,int,int> tu=Q.top(); Q.pop(); // cout << get<0>(tu) << " " << get<1>(tu) << " " << get<2>(tu) << " " << get<3>(tu) << ":\n"; if (il*get<2>(tu) >= get<1>(tu)) { // cout << "\tif1 wyn+=" << get<1>(tu) << "\n"; wyn+=get<1>(tu); } else { // cout << "\tif2 wyn+=" << il << "\n"; wyn+=il; if(get<2>(tu)>=2) Q.push({ get<1>(tu)-il-1, get<1>(tu)-il-1, 1}); il++; } } cout << wyn << "\n"; } }
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 | #include <bits/stdc++.h> using namespace std; priority_queue<tuple<int,int,int>> Q; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int test,n,wyn,i,dl,il; bool xd; char a; cin >> test; while(test--) { wyn=0; while(Q.size()) Q.pop(); cin >> n; for(i=1, dl=0, xd=1; i<=n; i++) { cin >> a; if(a=='1') { wyn++; if(dl>0) { Q.push({dl/(xd ? 1 : 2), dl, (xd ? 1 : 2)}); } xd=0; dl=0; } else dl++; } if(dl>0) { Q.push({dl, dl, 1}); } il=0; while(Q.size()) { tuple<int,int,int> tu=Q.top(); Q.pop(); // cout << get<0>(tu) << " " << get<1>(tu) << " " << get<2>(tu) << " " << get<3>(tu) << ":\n"; if (il*get<2>(tu) >= get<1>(tu)) { // cout << "\tif1 wyn+=" << get<1>(tu) << "\n"; wyn+=get<1>(tu); } else { // cout << "\tif2 wyn+=" << il << "\n"; wyn+=il; if(get<2>(tu)>=2) Q.push({ get<1>(tu)-il-1, get<1>(tu)-il-1, 1}); il++; } } cout << wyn << "\n"; } } |