#include <iostream> #include <string> #include <queue> #include <vector> #include <algorithm> using namespace std; void solve(){ int n; cin >> n; string cities; cin >> cities; priority_queue<int> middle_dist; vector<int> edge_dist(2, -1); for(int i = 0; i < n; i++) { if(cities[i] == '1') { edge_dist[0] = i; break; } } if(edge_dist[0] == -1) { cout << "0\n"; return; } for(int i = n - 1; i >= edge_dist[0]; i--) { if(cities[i] == '1') { edge_dist[1] = (n - 1) - i; break; } } int result = 1; int last_city = edge_dist[0]; for(int i = edge_dist[0] + 1; i <= (n - 1) - edge_dist[1]; i++) { if(cities[i] == '1') { if(i - last_city - 1 > 0) middle_dist.push(i - last_city - 1); last_city = i; result++; } } if(edge_dist[0] < edge_dist[1]) swap(edge_dist[0], edge_dist[1]); for(int i = 0; i < n; i++) { if(middle_dist.empty() && edge_dist[0] == 0) break; if(edge_dist[0] - i >= max((middle_dist.empty() ? 0 : middle_dist.top() - 2 * i - 2), 1)) { result += min(edge_dist[0], i); edge_dist[0] = 0; swap(edge_dist[0], edge_dist[1]); continue; } if(!middle_dist.empty() && middle_dist.top() <= i * 2) { while(!middle_dist.empty()) { result += middle_dist.top(); middle_dist.pop(); } } if(!middle_dist.empty()) { if(middle_dist.top() == i * 2 + 1 || middle_dist.top() == i * 2 + 2) result += middle_dist.top() - 1; else { result += i * 2 + 1; i++; } middle_dist.pop(); } } result += edge_dist[0] + edge_dist[1]; cout << result << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); long long z; cin>>z; while(z--){ solve(); } 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 | #include <iostream> #include <string> #include <queue> #include <vector> #include <algorithm> using namespace std; void solve(){ int n; cin >> n; string cities; cin >> cities; priority_queue<int> middle_dist; vector<int> edge_dist(2, -1); for(int i = 0; i < n; i++) { if(cities[i] == '1') { edge_dist[0] = i; break; } } if(edge_dist[0] == -1) { cout << "0\n"; return; } for(int i = n - 1; i >= edge_dist[0]; i--) { if(cities[i] == '1') { edge_dist[1] = (n - 1) - i; break; } } int result = 1; int last_city = edge_dist[0]; for(int i = edge_dist[0] + 1; i <= (n - 1) - edge_dist[1]; i++) { if(cities[i] == '1') { if(i - last_city - 1 > 0) middle_dist.push(i - last_city - 1); last_city = i; result++; } } if(edge_dist[0] < edge_dist[1]) swap(edge_dist[0], edge_dist[1]); for(int i = 0; i < n; i++) { if(middle_dist.empty() && edge_dist[0] == 0) break; if(edge_dist[0] - i >= max((middle_dist.empty() ? 0 : middle_dist.top() - 2 * i - 2), 1)) { result += min(edge_dist[0], i); edge_dist[0] = 0; swap(edge_dist[0], edge_dist[1]); continue; } if(!middle_dist.empty() && middle_dist.top() <= i * 2) { while(!middle_dist.empty()) { result += middle_dist.top(); middle_dist.pop(); } } if(!middle_dist.empty()) { if(middle_dist.top() == i * 2 + 1 || middle_dist.top() == i * 2 + 2) result += middle_dist.top() - 1; else { result += i * 2 + 1; i++; } middle_dist.pop(); } } result += edge_dist[0] + edge_dist[1]; cout << result << "\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); long long z; cin>>z; while(z--){ solve(); } return 0; } |