← 返回题目列表

Codeforces · 1945/C

C. 左右房子

中文机器翻译题面 查看原题

在Letovo村,有$$$n$$$房屋。村民们决定修建一条大路,将村庄分为左右两侧。每个居民都希望住在街道的右侧或左侧,这被描述为序列 $$$a_1, a_2, \dots, a_n$$$,其中 $$$a_j = 0$$$ 如果第 $$$j$$$ 房子的居民希望住在街道的左侧;否则,$$$a_j = 1$$$。

道路将经过两栋房屋之间。其左侧的房屋将被宣布为左侧,右侧的房屋将被宣布为右侧。更正式地说,让道路在房屋 $$$i$$$ 和 $$$i+1$$$ 之间通过。那么 $$$1$$$ 和 $$$i$$$ 之间位置的房屋将位于街道的左侧,$$$i+1$$$ 和 $$$n$$$ 之间位置的房屋将位于街道右侧。道路也可能经过第一座房子之前和最后一座房子之后;在这种情况下,整个村庄分别被声明为右侧或左侧。

为了使设计公平,决定铺设道路,以使村庄两侧至少有一半的居民对这一选择感到满意。也就是说,一侧的 $$$x$$$ 居民中,至少 $$$\lceil\frac{x}{2}\rceil$$$ 应该希望居住在该侧,其中 $$$\lceil x \rceil$$$ 表示对实数 $$$x$$$ 进行四舍五入。

路的左边有$$$i$$$个房屋,对应的$$$a_j$$$中至少有$$$\lceil\frac{i}{2}\rceil$$$个零。路的右边有$$$n-i$$$间房屋,对应的$$$a_j$$$间至少有$$$\lceil\frac{n-i}{2}\rceil$$$间。

确定道路应铺设在哪栋房子 $$$i$$$ 后,以满足所描述的条件,并尽可能靠近村庄的中心。形式上,在所有合适的位置 $$$i$$$ 中,最小化 $$$\left|\frac{n}{2} - i\right|$$$。

如果存在多个合适的位置$$$i$$$且最小$$$\left|\frac{n}{2} - i\right|$$$,则输出较小的那个。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3\cdot 10^5$$$)。每个测试用例的下一行包含一个长度为$$$n$$$的字符串$$$a$$$,仅由$$$0$$$和$$$1$$$组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例,输出一个数字$$$i$$$——应该在其后铺设道路的房屋的位置(如果应铺设在第一栋房屋之前,则输出$$$0$$$)。我们可以证明答案总是存在的。

示例

输入 #1

7
3
101
6
010111
6
011001
3
000
3
110
3
001
4
1100

输出 #1

2
3
2
3
0
1
0

注意

让我们考虑输入数据的第一个示例。

如果我们在第一栋房子之后铺设道路,那么街道左侧将有一个房子 $$$a_1 = 1$$$,其中的居民希望住在街道右侧。那么,偶数一侧的 $$$1$$$ 居民中的 $$$0$$$ 都会对这个选择感到满意,这意味着道路不能铺设在房子 $$$1$$$ 之后。

如果我们在第二栋房子之后铺设道路,左侧 $$$2$$$ 居民中的 $$$1$$$(优先选择 $$$a_1 = 1$$$、$$$a_2 = 0$$$)和右侧 $$$1$$$ 居民中的 $$$1$$$(优先选择 $$$a_3 = 1$$$)会对这一选择感到满意。两边超过一半的居民对这个选择感到满意,这意味着道路可以在房子$$$2$$$之后铺设。我们可以证明这是最佳答案。