Heavy Intervals

题目描述

Shiki - Pure Ruby

⠀

你有 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$，其中对于每个 $i$，都有 $l_i < r_i$，并且所有区间的端点都是互不相同的。

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

你不喜欢大的权值，所以你希望使所有区间的权值和尽可能小。你可以进行以下三种操作：

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

但是，所有操作完成后，区间仍需合法（即对于每个 $i$，都要满足 $l_i < r_i$）。

在进行操作后，区间权值和的最小可能值是多少？

输入格式

每个测试点包含多组测试用例。第一行包含一个整数 $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 < 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$。

输出格式

对于每个测试用例，输出一个整数，表示经过操作后所有区间权值和的最小可能值。

输入输出样例 #1

输入 #1

2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3

输出 #1

2400
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$ 更小的权值和的区间配置。

由 ChatGPT 4.1 翻译