P16707 [SEATST 2026] 车辆集结 / Car Gathering

数轴上有 $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)$ 最小值，你可以返回其中任意一个。 ### 实现详情 你需要实现以下函数。 ```cpp int car_gathering(int N, std::vector X, std::vector 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` 的返回值。

### 样例 考虑以下函数调用： ```cpp 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$ 分) 没有额外的约束。