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
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t,n;
	string a;
	cin>>t;
	for(int i=0; i<t; i++){
		cin>>n>>a;
		bool czy=1;
		int ile=0;
		vector <pair <int, int>> v;
		for(int j=0; j<n; j++){
			while(j<n&&a[j]=='0'){
				ile++;
				j++;
			}
			if(j==n){
				v.push_back(make_pair(ile, 1));
			}
			else if(czy){
				v.push_back(make_pair(ile, czy));
			}
			else{
				v.push_back(make_pair(ile-1, czy));
			}
			czy=0;
			ile=0;
		}
		sort(v.begin(), v.end());
		int wynik=n;
		int iledni=0;
		for(int j=v.size()-1; j>=0; j--){
			if(v[j].second==1&&v[j].first-iledni>0){
				wynik-=v[j].first-iledni;
				iledni++;
			}
			else if(v[j].second==0&&v[j].first-2*iledni>0){
				wynik-=v[j].first-2*iledni;
				iledni+=2;
			}
			else if(v[j].second==0&&v[j].first-2*iledni==0){
				wynik-=1;
				iledni+=1;
			}
		}
		cout<<wynik<<endl;
	}
}