CF1622B Berland Music

Berland Music 是一个专为支持 Berland 本地艺术家而打造的音乐流媒体服务。其开发者目前正在开发一套歌曲推荐模块。 假设 Monocarp 收到了 $n$ 首推荐歌曲，编号从 $1$ 到 $n$。第 $i$ 首歌的预测评分为 $p_i$，其中 $1 \le p_i \le n$，且 $1$ 到 $n$ 的每个整数恰好出现一次。换句话说，$p$ 是一个排列。 在听完每首歌后，Monocarp 会按下“喜欢”或“不喜欢”按钮。用一个字符串 $s$ 表示他的投票序列，其中 $s_i=0$ 表示他不喜欢第 $i$ 首歌，$s_i=1$ 表示他喜欢第 $i$ 首歌。 现在，服务需要重新评估这些歌曲的评分，使得： - 新的评分 $q_1, q_2, \dots, q_n$ 仍然构成一个排列（$1 \le q_i \le n$，每个整数 $1$ 到 $n$ 恰好出现一次）； - Monocarp 喜欢的每首歌的评分都要高于他不喜欢的每首歌（形式化地说，对于所有满足 $s_i=1$ 且 $s_j=0$ 的 $i, j$，都应有 $q_i > q_j$）。 在所有满足条件的排列 $q$ 中，找到一个使得 $\sum\limits_{i=1}^n |p_i-q_i|$ 最小的排列，其中 $|x|$ 表示 $x$ 的绝对值。 输出排列 $q_1, q_2, \dots, q_n$。如果有多个答案，可以输出任意一个。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示歌曲数量。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$），表示预测评分的排列。 第三行包含一个长度为 $n$ 的字符串 $s$，每个字符为 $0$ 或 $1$。$0$ 表示 Monocarp 不喜欢该歌曲，$1$ 表示喜欢。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行 $n$ 个整数，表示重新评估后的歌曲评分排列 $q$。如果有多个使 $\sum\limits_{i=1}^n |p_i-q_i|$ 最小的答案，可以输出任意一个。

在第一个测试用例中，只有一种排列 $q$ 能满足所有喜欢的歌评分高于所有不喜欢的歌：第 $1$ 首歌评分为 $2$，第 $2$ 首歌评分为 $1$。$\sum\limits_{i=1}^n |p_i-q_i|=|1-2|+|2-1|=2$。 在第二个测试用例中，Monocarp 喜欢所有歌曲，因此所有排列都可以。使绝对差之和最小的排列是 $p$ 本身，其代价为 $0$。 由 ChatGPT 4.1 翻译