logo AlgoBeat OnlineJudge
登录 注册

#216697. [SEATST 2026] 车辆集结 / Car Gathering

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

数轴上有 辆汽车,编号从 。给定它们的位置列表 以及它们每单位的耗油率列表 ,每个列表都已按顺序排序。然而,你不知道哪辆汽车对应哪个位置或哪个耗油率。但你知道每辆汽车都有确切的一个位置和确切的一个耗油率。

也就是说,存在两个长度为 的排列 ,使得第 辆汽车位于位置 且其耗油率为

::::info[什么是长度为 的排列?]{open} 在这道题中,长度为 的排列 是一个长度为 的数组,满足对于所有 都有 ,并且对于所有 都有

例如, 是一个长度为 的排列,但 不是长度为 的排列。 ::::

给定一个特定的分配 ,我们将所有汽车集结在点 的总燃料成本定义为

给定一个 整数 ,定义在点 最坏情况燃料成本 为所有可能的分配 下的最大总燃料成本。也就是说,定义

你的任务是找一个整数点 ,使得在点 的最坏情况燃料成本 最小化。如果有多个点 都能达到相同的 最小值,你可以返回其中任意一个。

实现详情

你需要实现以下函数。

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

输入格式

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])

假设 。可以证明,分配 会产生 最坏情况燃料成本 。也就是说, 。请注意,可能还有其他 的分配方式也能产生 最坏情况燃料成本 ,例如

同时也可以证明,整数点 是导致 最小值的点。因此,该函数调用该返回 1。

约束

  • 对于所有
  • 对于所有
  • 对于所有
  • 对于所有

子任务

  1. ( 分)
  2. ( 分)
  3. ( 分)
  4. ( 分) 对于所有
  5. ( 分) 没有额外的约束。