当前位置: 首页> 教育> 培训 > 软件编程代码大全_郑州网站制作方案_sem推广和seo的区别_厦门百度seo公司

软件编程代码大全_郑州网站制作方案_sem推广和seo的区别_厦门百度seo公司

时间:2025/7/11 23:34:28来源:https://blog.csdn.net/jj12345jj198999/article/details/144778029 浏览次数:0次
软件编程代码大全_郑州网站制作方案_sem推广和seo的区别_厦门百度seo公司

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:

  1. delete one character from ss. This operation costs 11 coin;
  2. 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;
}

关键字:软件编程代码大全_郑州网站制作方案_sem推广和seo的区别_厦门百度seo公司

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: