time limit per test
1 second
memory limit per test
256 megabytes
You are given a binary string ss (a string consisting only of 0-s and 1-s).
You can perform two types of operations on ss:
- delete one character from ss. This operation costs 11 coin;
- swap any pair of characters in ss. This operation is free (costs 00 coins).
You can perform these operations any number of times and in any order.
Let's name a string you've got after performing operations above as tt. The string tt is good if for each ii from 11 to |t||t| ti≠siti≠si (|t||t| is the length of the string tt). The empty string is always good. Note that you are comparing the resulting string tt with the initial string ss.
What is the minimum total cost to make the string tt good?
Input
The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.
The only line of each test case contains a binary string ss (1≤|s|≤2⋅1051≤|s|≤2⋅105; si∈{si∈{0, 1}}) — the initial string, consisting of characters 0 and/or 1.
Additional constraint on the input: the total length of all strings ss doesn't exceed 2⋅1052⋅105.
Output
For each test case, print one integer — the minimum total cost to make string tt good.
Example
Input
Copy
4
0
011
0101110001
111100
Output
Copy
1 1 0 4
Note
In the first test case, you have to delete a character from ss to get the empty string tt. Only then tt becomes good. One deletion costs 11 coin.
In the second test case, you can, for example, delete the second character from ss to get the string 01, and then swap the first and second characters to get the string tt == 10. String tt is good, since t1≠s1t1≠s1 and t2≠s2t2≠s2. The total cost is 11 coin.
In the third test case, you can, for example, swap s1s1 with s2s2, swap s3s3 with s4s4, swap s5s5 with s7s7, s6s6 with s8s8 and s9s9 with s10s10. You'll get tt == 1010001110. All swap operations are free, so the total cost is 00.
解题说明：此题是一道模拟题，最多消耗1和0的个数总和，否则就统计10组合的数字进行变换。
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int main()
{int n;cin >> n;while (n--){string s;cin >> s;int a = 0, b = 0;for (int i = 0; s[i]; i++){ if (s[i] == '1'){a++;}else{b++;}}int ans = a + b;int a1 = 0, b1 = 0;for (int i = 0; s[i]; i++){if (s[i] == '1'){b1++;}else{a1++;}if (a1 > a || b1 > b){break;}ans = min(ans, a + b - a1 - b1);}cout << ans << endl;}return 0;
}
