AT_abc257_c [ABC257C] Robot Takahashi

题目描述

有 $N$ 个人，每个人要么是小孩，要么是大人。第 $i$ 个人的体重为 $W_i$ 。

给定一个长度为 $N$ 的字符串 $S$ ，若 $S$ 的第 $i$ 个字符为0，则第 $i$ 个人为小孩；若 $S$ 的第 $i$ 个字符为1，第 $i$ 个人为大人。

高桥君认为，如果一个人体重小于 $X$ ，则他是小孩；如果一个人体重大于等于 $X$ ，则他是大人。

请选择合适的实数 $X$ ，使得高桥君判断正确的人数最大。输出这个最大值。

数据范围

$1 \leq N \leq 2×10^5$

$S$ 是一个长度为 $N$ 且仅含0、1的字符串。

$1 \leq W_i \leq 10^9$

保证 $N$ 和 $W_i$ 都是整数。

输入格式

数据以下列形式给出：

$N$

$S$

$W_1$ $W_2$ … $W_N$

输出格式

选择合适的实数 $X$ ，使得高桥君判断正确的人数最大。输出这个最大值，并在末尾换行。

样例解释

样例1

高桥君可以令 $X=50$ ，他判定第 $2,3,4$ 个人为小孩，其他人为大人。实际上，只有第 $2,4$ 个人为小孩，其他人为大人。高桥君判断正确了第 $1,2,4,5$ 个人，一共 $4$ 个人。这是最大值。

样例2

高桥君可以令 $X=10$ ，三个人都将判断正确。注意，有可能所有人都是大人，也有可能所有人都是小孩。

样例3

高桥君可以令 $X=55$ ，他将判断正确了 $4$ 个人。这是最大值。注意，可能会有两个人的体重相同。

输入输出样例 #1

输入 #1

5
10101
60 45 30 40 80

输出 #1

4

输入输出样例 #2

输入 #2

3
000
1 2 3

输出 #2

3

输入输出样例 #3

输入 #3

5
10101
60 50 50 50 60

输出 #3

4