题目描述

在Letovo村庄里有n栋房子。村民们决定修建一条大街，将村庄分为左右两侧。每位居民都希望住在街道的左侧或右侧，这可以用序列a1,a2,…,an来描述，其中如果第j栋房子的居民想住在街道的左侧，则aj=0；否则，aj=1。

道路将穿过两栋房子。它左侧的房子将被宣布为左侧，右侧的房子将被宣布为右侧。更正式地，让道路穿过第i和第i+1栋房子。然后在位置1到i之间的房子将位于街道的左侧，在位置i+1到n之间的房子将位于右侧。道路也可能在第一栋房子之前或最后一栋房子之后通过；在这种情况下，整个村庄分别被宣布为右侧或左侧。

为了使设计公平，决定铺设道路，以便村庄每一侧至少有一半的居民对选择感到满意。也就是说，在一侧的x位居民中，至少应有⌈x/2⌉位希望住在该侧，其中⌈x⌉表示将实数x向上取整。

在道路的左侧，将有i栋房子，对应的aj中必须至少有⌈i/2⌉个零。在道路的右侧，将有n−i栋房子，对应的aj中必须至少有⌈n−i/2⌉个一。

确定道路应该铺设在哪栋房子之后，以满足所描述的条件，并尽可能靠近村庄的中间位置。形式上，对于所有合适的位置i，最小化∣∣n/2−i∣∣。

如果有多个最小∣∣n/2−i∣∣的合适位置i，则输出较小的一个。

输入 每个测试包含多个测试用例。第一行包含测试用例数量t（1≤t≤2⋅10^4）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数n（3≤n≤3⋅10^5）。每个测试用例的下一行包含一个长度为n的字符串a，只包含0和1。

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

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

output

 解题思路

前缀和一下0和1，然后遍历一遍，取最小值，注意：如果存在多个解取最靠中间的，如果靠中间的程度相同优先取左边

题目描述

有一群人排成一队，共有n个人，从第一个人i=1开始，向Serafim the Owl询问生命的意义。不幸的是，Kirill因为忙着为这个问题编写传奇故事，所以他稍晚到了一点，站在第n个人之后的队尾。Kirill对这种情况非常不满，所以他决定贿赂一些在他前面的人。

对于队列中的第i个人，Kirill知道两个值：ai和bi。如果此时Kirill站在位置i，那么他可以选择任何位置j，使得j= 1; i--) { if (hhh > a[i] + he[i + 1] - he[u]) hhh = a[i] + he[i + 1] - he[u]; } sum += hhh; } printf("%lld\n", sum); } return 0; }