CF1909C.Heavy Intervals

Shiki - Pure Ruby

⠀

You have $n$ intervals $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$, such that $l_i \lt r_i$ for each $i$, and all the endpoints of the intervals are distinct.

The $i$-th interval has weight $c_i$ per unit length. Therefore, the weight of the $i$-th interval is $c_i \cdot (r_i - l_i)$.

You don't like large weights, so you want to make the sum of weights of the intervals as small as possible. It turns out you can perform all the following three operations:

• rearrange the elements in the array $l$ in any order;
• rearrange the elements in the array $r$ in any order;
• rearrange the elements in the array $c$ in any order.

However, after performing all of the operations, the intervals must still be valid (i.e., for each $i$, $l_i \lt r_i$ must hold).

What's the minimum possible sum of weights of the intervals after performing the operations?

Shiki - Pure Ruby

⠀

你有 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$，满足对每个 $i$ 都有 $l_i \lt r_i$，且所有区间的端点互不相同。

第 $i$ 个区间的单位长度权重为 $c_i$，因此第 $i$ 个区间的总权重为 $c_i \cdot (r_i - l_i)$。

你不喜欢过大的权重，因此希望使所有区间的权重之和尽可能小。事实上，你可以执行以下三种操作（任意顺序、任意次数）：

• 以任意顺序重排数组 $l$ 中的元素；
• 以任意顺序重排数组 $r$ 中的元素；
• 以任意顺序重排数组 $c$ 中的元素。

但操作完成后，所有区间仍必须保持有效（即对每个 $i$，都必须满足 $l_i \lt r_i$）。

在执行上述操作后，区间的权重之和可能达到的最小值是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of intervals.

The second line of each test case contains $n$ integers $l_1, l_2, \ldots, l_n$ ($1 \le l_i \le 2 \cdot 10^5$) — the left endpoints of the initial intervals.

The third line of each test case contains $n$ integers $r_1, r_2, \ldots, r_n$ ($l_i \lt r_i \le 2 \cdot 10^5$) — the right endpoints of the initial intervals.

It is guaranteed that ${l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n}$ are all distinct.

The fourth line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^7$) — the initial weights of the intervals per unit length.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 区间的数量。

每个测试用例的第二行包含 $n$ 个整数 $l_1, l_2, \ldots, l_n$（$1 \le l_i \le 2 \cdot 10^5$）—— 初始区间的左端点。

每个测试用例的第三行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n$（$l_i \lt r_i \le 2 \cdot 10^5$）—— 初始区间的右端点。

保证集合 $\{l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n\}$ 中所有元素互不相同。

每个测试用例的第四行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 10^7$）—— 各区间初始的单位长度权重。

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

For each test case, output a single integer: the minimum possible sum of weights of the intervals after your operations.

对于每个测试用例，输出一个整数：经过你的操作后，区间的权重之和的最小可能值。

In the first test case, you can make

• $l = [8, 3]$;
• $r = [23, 12]$;
• $c = [100, 100]$.

In that case, there are two intervals:

• interval $[8, 23]$ with weight $100$ per unit length, and $100 \cdot (23-8) = 1500$ in total;
• interval $[3, 12]$ with weight $100$ per unit length, and $100 \cdot (12-3) = 900$ in total.

The sum of the weights is $2400$. It can be shown that there is no configuration of final intervals whose sum of weights is less than $2400$.

In the second test case, you can make

• $l = [1, 2, 5, 20]$;
• $r = [3, 4, 10, 30]$;
• $c = [3, 3, 2, 2]$.

In that case, there are four intervals:

• interval $[1, 3]$ with weight $3$ per unit length, and $3 \cdot (3-1) = 6$ in total;
• interval $[2, 4]$ with weight $3$ per unit length, and $3 \cdot (4-2) = 6$ in total;
• interval $[5, 10]$ with weight $2$ per unit length, and $2 \cdot (10-5) = 10$ in total;
• interval $[20, 30]$ with weight $2$ per unit length, and $2 \cdot (30-20) = 20$ in total.

The sum of the weights is $42$. It can be shown that there is no configuration of final intervals whose sum of weights is less than $42$.

在第一个测试用例中，你可以构造：

• $l = [8, 3]$；
• $r = [23, 12]$；
• $c = [100, 100]$。

此时存在两个区间：

• 区间 $[8, 23]$，单位长度权重为 $100$，总权重为 $100 \cdot (23-8) = 1500$；
• 区间 $[3, 12]$，单位长度权重为 $100$，总权重为 $100 \cdot (12-3) = 900$。

权重总和为 $2400$。可以证明，不存在任何最终区间的构造方案，使其权重总和小于 $2400$。

在第二个测试用例中，你可以构造：

• $l = [1, 2, 5, 20]$；
• $r = [3, 4, 10, 30]$；
• $c = [3, 3, 2, 2]$。

此时存在四个区间：

• 区间 $[1, 3]$，单位长度权重为 $3$，总权重为 $3 \cdot (3-1) = 6$；
• 区间 $[2, 4]$，单位长度权重为 $3$，总权重为 $3 \cdot (4-2) = 6$；
• 区间 $[5, 10]$，单位长度权重为 $2$，总权重为 $2 \cdot (10-5) = 10$；
• 区间 $[20, 30]$，单位长度权重为 $2$，总权重为 $2 \cdot (30-20) = 20$。

权重总和为 $42$。可以证明，不存在任何最终区间的构造方案，使其权重总和小于 $42$。