4

我正在尝试解决这个问题：http ://acm.tju.edu.cn/toj/showp2886.html

我尝试了一些解决方案，我将解释其中的两个。请注意，两者都假设成本（位置）是一个凸函数，这意味着它向中间递减（实际上是向中间值（供应点）的某处），并且图表看起来或多或少像 U 形。

  1. 找到cost(position) <= M的最左边和最右边的补给点位置。找到最小值和最大值后，我试着看看能不能把间隔弄大一点（因为餐厅不一定是地方正好在一个供应点上）。这是一个很好的解决方案，但需要非常多的时间来计算最后一位。它在 M 非常大且供应点很少且成本最低的测试中失败。复杂度：O(NlogN) + O(M)。下面的这个解决方案超出了时间限制，但我尝试了另一个解决方案，我在 O(1) 中计算我可以在两个方向上走多少，我得到了错误的答案。

  2. 由于函数是凸函数，我可以使用三元搜索来找到最小值。如果最小值小于 M，则二分查找函数的下界和上界（即 M）。复杂性：O(NlogM)，因为对于每个 O(logM)，我都会计算 O(N) 中的成本。

这是我尝试过的，但我仍然得到“错误答案”，所以我需要一些帮助，因为这让我发疯。

这个问题在规格中并不是很清楚（或者至少我是这么认为的），因为当我第一次阅读它时，我不认为成本是从所有供应点计算的，而是从最近的供应点计算的。该示例清除了这一点。另外，我不知道我的成本（位置）函数是凸的假设是否真的正确。但是我尝试了很多例子，看起来确实如此。

谢谢。任何帮助表示赞赏。:D

4

1 回答 1

1

列表中两个连续供应商位置之间的最小客观值必须出现在两个供应商位置之一。要了解这一点，请考虑两个供应商位置之间没有供应商位置，它们的位置相差超过 1。假设左侧供应商位置提供的客观价值小于或等于右侧供应商位置。然后，每次您从左侧供应商位置开始向右移动 1 步时，目标函数都会上升（很弱，它可能会保持不变），因为目标函数的变化量与您在右侧移动 1 步时的变化量相同两个连续供应商位置之间的时间。因此，您唯一需要计算的是有多少供应商位置提供相同的全局最小值。

请注意，根据我的分析，有可能有两个不连续的段给出相同的全局最小目标值。如果是这样，那么您的函数可能不是凸函数，这可能是您当前尝试中遇到困难的根源。

对于 N 个供应商，从左到右计算每个供应商位置的目标值可以在 O(N) 时间内完成。

于 2015-04-15T17:56:31.620 回答