Balanced String
题意翻译
给你一个长为 $n$ 的 $01$ 字符串,每次操作交换两个元素,求最少几次操作能使字符串的顺序对个数与逆序对个数相等。
题目描述
You are given a binary string $ s $ (a binary string is a string consisting of characters 0 and/or 1).
Let's call a binary string balanced if the number of subsequences 01 (the number of indices $ i $ and $ j $ such that $ 1 \le i < j \le n $ , $ s_i=0 $ and $ s_j=1 $ ) equals to the number of subsequences 10 (the number of indices $ k $ and $ l $ such that $ 1 \le k < l \le n $ , $ s_k=1 $ and $ s_l=0 $ ) in it.
For example, the string 1000110 is balanced, because both the number of subsequences 01 and the number of subsequences 10 are equal to $ 6 $ . On the other hand, 11010 is not balanced, because the number of subsequences 01 is $ 1 $ , but the number of subsequences 10 is $ 5 $ .
You can perform the following operation any number of times: choose two characters in $ s $ and swap them. Your task is to calculate the minimum number of operations to make the string $ s $ balanced.
输入输出格式
输入格式
The only line contains the string $ s $ ( $ 3 \le |s| \le 100 $ ) consisting of characters 0 and/or 1.
Additional constraint on the input: the string $ s $ can be made balanced.
输出格式
Print a single integer — the minimum number of swap operations to make the string $ s $ balanced.
输入输出样例
输入样例 #1
101
输出样例 #1
0
输入样例 #2
1000110
输出样例 #2
0
输入样例 #3
11010
输出样例 #3
1
输入样例 #4
11001100
输出样例 #4
2
说明
In the first example, the string is already balanced, the number of both 01 and 10 is equal to $ 1 $ .
In the second example, the string is already balanced, the number of both 01 and 10 is equal to $ 6 $ .
In the third example, one of the possible answers is the following one: 11010 $ \rightarrow $ 01110. After that, the number of both 01 and 10 is equal to $ 3 $ .
In the fourth example, one of the possible answers is the following one: 11001100 $ \rightarrow $ 11001010 $ \rightarrow $ 11000011. After that, the number of both 01 and 10 is equal to $ 8 $ .