数轴上有 辆汽车,编号从 到 。给定它们的位置列表 以及它们每单位的耗油率列表 ,每个列表都已按顺序排序。然而,你不知道哪辆汽车对应哪个位置或哪个耗油率。但你知道每辆汽车都有确切的一个位置和确切的一个耗油率。
也就是说,存在两个长度为 的排列 和 ,使得第 辆汽车位于位置 且其耗油率为 。
::::info[什么是长度为 的排列?]{open}
在这道题中,长度为 的排列 是一个长度为 的数组,满足对于所有 都有 ,并且对于所有 都有 。
例如, 是一个长度为 的排列,但 和 不是长度为 的排列。
::::
给定一个特定的分配 ,我们将所有汽车集结在点 的总燃料成本定义为 。
给定一个 整数 点 ,定义在点 的 最坏情况燃料成本 为所有可能的分配 下的最大总燃料成本。也就是说,定义 。
你的任务是找一个整数点 ,使得在点 的最坏情况燃料成本 最小化。如果有多个点 都能达到相同的 最小值,你可以返回其中任意一个。
实现详情
你需要实现以下函数。
int car_gathering(int N, std::vector<int> X, std::vector<int> C)
- :汽车的数量。
- :一个长度为 的数组,描述了按顺序排序的汽车位置。
- :一个长度为 的数组,描述了按顺序排序的汽车油耗率。
- 对于每个测试数据,此函数恰好被调用一次。
- 此函数应返回一个整数 ,使得在所有整点中,将所有汽车集结在 点的最坏情况燃料成本最小。