#CF2266C. AND, OR, Sort!
AND, OR, Sort!
题目描述
给定一个长度为 的二进制字符串 。
你可以执行以下操作任意次数(可以为零):
注意,单个元素的按位与或按位或等于该元素本身。
你的目标是使 按非降序排列。
求使 按非降序排列所需的最少操作次数。
二进制字符串仅包含字符 和 。
若 按非降序排列,则 。
输入格式
第一行包含一个整数 ()— 测试用例的数量。
每个测试用例的第一行包含一个整数 ()— 二进制字符串 的长度。
每个测试用例的第二行包含长度为 的二进制字符串 。 的每个字符要么是 0 要么是 1。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,输出一个整数 — 使 按非降序排列所需的最少操作次数。
样例
6
4
0011
4
1000
5
01000
8
01001101
7
0101010
7
0111101
0
3
1
2
3
1
说明
在第一个测试用例中,字符串已经有序,因此不需要任何操作。
在第二个测试用例中,可以使用按位或将最后三个字符变为 1,经过 次操作得到 1111。
来源
导入自 Codeforces — Codeforces Round 1122 (Div. 3)。