Glory Addicts

题意翻译

给定一个长度为 $n$（$1\le n \le 10^5$） 的序列，这个序列中的第 $i$ 个元素都可以用一个二元组 $(a_i,b_i)$ 表示（$a=0$ 或 $1$，$1\le b\le 10^9$）。 定义这个序列中第 $i$ 个元素的价值为： $\begin{cases} b_i\ ,i=1\ 或\ a_i=a_{i-1} \\ 2\times b_i\ ,\ a_i \ne a_i-1 \end{cases}$ 可以重新排列这个序列，最大化这个序列的每个元素的价值和。 多组数据，保证输入的 $n$ 的和不大于 $10^5$，数据组数 $t\le 10^5$。

题目描述

The hero is addicted to glory, and is fighting against a monster. The hero has $ n $ skills. The $ i $ -th skill is of type $ a_i $ (either fire or frost) and has initial damage $ b_i $ . The hero can perform all of the $ n $ skills in any order (with each skill performed exactly once). When performing each skill, the hero can play a magic as follows: - If the current skill immediately follows another skill of a different type, then its damage is doubled. In other words, 1. If a skill of type fire and with initial damage $ c $ is performed immediately after a skill of type fire, then it will deal $ c $ damage; 2. If a skill of type fire and with initial damage $ c $ is performed immediately after a skill of type frost, then it will deal $ 2c $ damage; 3. If a skill of type frost and with initial damage $ c $ is performed immediately after a skill of type fire, then it will deal $ 2c $ damage; 4. If a skill of type frost and with initial damage $ c $ is performed immediately after a skill of type frost , then it will deal $ c $ damage. Your task is to find the maximum damage the hero can deal.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 10^5 $ ), indicating the number of skills. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \leq a_i \leq 1 $ ), where $ a_i $ indicates the type of the $ i $ -th skill. Specifically, the $ i $ -th skill is of type fire if $ a_i = 0 $ , and of type frost if $ a_i = 1 $ . The third line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \leq b_i \leq 10^9 $ ), where $ b_i $ indicates the initial damage of the $ i $ -th skill. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output the maximum damage the hero can deal.

输入输出样例

输入样例 #1

4
4
0 1 1 1
1 10 100 1000
6
0 0 0 1 1 1
3 4 5 6 7 8
3
1 1 1
1000000000 1000000000 1000000000
1
1
1

输出样例 #1

2112
63
3000000000
1

说明

In the first test case, we can order the skills by $ [3, 1, 4, 2] $ , and the total damage is $ 100 + 2 \times 1 + 2 \times 1000 + 10 = 2112 $ . In the second test case, we can order the skills by $ [1, 4, 2, 5, 3, 6] $ , and the total damage is $ 3 + 2 \times 6 + 2 \times 4 + 2 \times 7 + 2 \times 5 + 2 \times 8 = 63 $ . In the third test case, we can order the skills by $ [1, 2, 3] $ , and the total damage is $ 1000000000 + 1000000000 + 1000000000 = 3000000000 $ . In the fourth test case, there is only one skill with initial damage $ 1 $ , so the total damage is $ 1 $ .

**题目大意：**

英雄对荣耀上瘾，正在与一个怪物战斗。英雄有 $ n $ 个技能，第 $ i $ 个技能的类型为 $ a_i $（火或冰），初始伤害为 $ b_i $。英雄可以以任意顺序执行所有 $ n $ 个技能（每个技能执行一次）。当执行每个技能时，如果当前技能紧随另一个不同类型的技能之后，那么它的伤害会加倍。

任务是最大化英雄可以造成的总伤害。

**输入输出数据格式：**

**输入格式：**

每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。接下来的行包含每个测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^5 $），表示技能的数量。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 0 \leq a_i \leq 1 $），其中 $ a_i $ 表示第 $ i $ 个技能的类型。具体来说，如果 $ a_i = 0 $，则第 $ i $ 个技能是火属性；如果 $ a_i = 1 $，则是冰属性。

每个测试用例的第三行包含 $ n $ 个整数 $ b_1, b_2, \dots, b_n $（$ 1 \leq b_i \leq 10^9 $），其中 $ b_i $ 表示第 $ i $ 个技能的初始伤害。

保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。

**输出格式：**

对于每个测试用例，输出英雄可以造成的最大伤害。**题目大意：** 英雄对荣耀上瘾，正在与一个怪物战斗。英雄有 $ n $ 个技能，第 $ i $ 个技能的类型为 $ a_i $（火或冰），初始伤害为 $ b_i $。英雄可以以任意顺序执行所有 $ n $ 个技能（每个技能执行一次）。当执行每个技能时，如果当前技能紧随另一个不同类型的技能之后，那么它的伤害会加倍。 任务是最大化英雄可以造成的总伤害。 **输入输出数据格式：** **输入格式：** 每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。接下来的行包含每个测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^5 $），表示技能的数量。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 0 \leq a_i \leq 1 $），其中 $ a_i $ 表示第 $ i $ 个技能的类型。具体来说，如果 $ a_i = 0 $，则第 $ i $ 个技能是火属性；如果 $ a_i = 1 $，则是冰属性。 每个测试用例的第三行包含 $ n $ 个整数 $ b_1, b_2, \dots, b_n $（$ 1 \leq b_i \leq 10^9 $），其中 $ b_i $ 表示第 $ i $ 个技能的初始伤害。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式：** 对于每个测试用例，输出英雄可以造成的最大伤害。