题目描述

数轴上有 $N$ 辆汽车，编号从 $0$ 到 $N - 1$ 。给定它们的位置列表 $X[0], X[1], \ldots, X[N - 1]$ 以及它们每单位的耗油率列表 $C[0], C[1], \ldots, C[N - 1]$ ，每个列表都已按顺序排序。然而，你不知道哪辆汽车对应哪个位置或哪个耗油率。但你知道每辆汽车都有确切的一个位置和确切的一个耗油率。

也就是说，存在两个长度为 $N$ 的排列 $P$ 和 $Q$ ，使得第 $i$ 辆汽车位于位置 $X[P[i]]$ 且其耗油率为 $C[Q[i]]$ 。

::::info[什么是长度为 $N$ 的排列？]{open} 在这道题中，长度为 $N$ 的排列 $P$ 是一个长度为 $N$ 的数组，满足对于所有 $0 \le i \le N - 1$ 都有 $0 \le P[i] \le N - 1$ ，并且对于所有 $0 \le i < j \le N - 1$ 都有 $P[i] \ne P[j]$ 。

例如，$[2, 1, 0]$ 是一个长度为 $3$ 的排列，但 $[1, 2, 3]$ 和 $[2, 0, 2]$ 不是长度为 $3$ 的排列。 ::::

给定一个特定的分配 $(P, Q)$ ，我们将所有汽车集结在点 $y$ 的总燃料成本定义为 $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} |X[P[i]] - y| \times C[Q[i]]$ 。

给定一个 整数 点 $p$ ，定义在点 $p$ 的 最坏情况燃料成本 为所有可能的分配 $(P, Q)$ 下的最大总燃料成本。也就是说，定义 $\text{worst}(p) = \max \limits_{P, Q} \text{cost}(P, Q, p)$ 。

你的任务是找一个整数点 $p$ ，使得在点 $p$ 的最坏情况燃料成本 $\text{worst}(p)$ 最小化。如果有多个点 $p$ 都能达到相同的 $\text{worst}(p)$ 最小值，你可以返回其中任意一个。

实现详情

你需要实现以下函数。

int car_gathering(int N, std::vector<int> X, std::vector<int> C)

• $N$ ：汽车的数量。
• $X$ ：一个长度为 $N$ 的数组，描述了按顺序排序的汽车位置。
• $C$ ：一个长度为 $N$ 的数组，描述了按顺序排序的汽车油耗率。
• 对于每个测试数据，此函数恰好被调用一次。
• 此函数应返回一个整数 $p$ ，使得在所有整点中，将所有汽车集结在 $p$ 点的最坏情况燃料成本最小。

输入格式

N
X[0] X[1] ... X[N - 1]
C[0] C[1] ... C[N - 1]

输出格式

一个整数，表示 car_gathering 的返回值。

提示

样例

考虑以下函数调用：

car_gathering(3, [-1, 2, 3], [1, 1, 2])

假设 $p = 1$ 。可以证明，分配 $P = [0, 1, 2]$ 和 $Q = [2, 1, 0]$ 会产生 最坏情况燃料成本 。也就是说， $\text{worst}(p) = \text{cost}(P, Q, p) = (|-1 - 1| \times 2) + (|2 - 1| \times 1) + (|3 - 1| \times 1) = 7$ 。请注意，可能还有其他 $P$ 和 $Q$ 的分配方式也能产生 最坏情况燃料成本 ，例如 $P = [2, 1, 0]$ 和 $Q = [2, 1, 0]$ 。

同时也可以证明，整数点 $p = 1$ 是导致 $\text{worst}(p)$ 最小值的点。因此，该函数调用该返回 1。

约束

• $1 \le N \le 10\ 000\ 000$ 。
• 对于所有 $0 \le i \le N - 1$ ， $-10^9 \le X[i] \le 10^9$ 。
• 对于所有 $0 \le i \le N - 1$ ， $0 \le C[i] \le 100$ 。
• 对于所有 $0 \le i < j \le N - 1$ ， $X[i] \le X[j]$ 。
• 对于所有 $0 \le i < j \le N - 1$ ， $C[i] \le C[j]$ 。

子任务

1. ($10$ 分) $N \le 1000$ ， $|X[i]| \le 10^3$ 。
2. ($23$ 分) $N \le 100\ 000$ 。
3. ($17$ 分) $N \le 1\ 000\ 000$ 。
4. ($31$ 分) 对于所有 $0 \le i \le N - 1$ ， $C[i] \le 1$ 。
5. ($19$ 分) 没有额外的约束。