algorithm - 解决 ACM TJU 2886 - 餐厅

Question

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

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

1. 找到成本(位置)<= M 的最左边和最右边的供应点位置。找到最小值和最大值后，我尝试看看是否可以使间隔大一点(因为餐厅没有'必须准确地放置在供应点上)。这是一个很好的解决方案，但需要非常多的时间来计算最后一位。它在 M 非常大且几乎没有最低成本的供应点的测试中失败。复杂度:O(NlogN) + O(M)。下面的解决方案超出了时间限制，但我尝试了另一个解决方案，我在 O(1) 中计算我可以在两个方向上走多少，但我得到了错误的答案。

2. 由于函数是凸函数，我可以使用三元搜索来找到最小值。如果最小值小于 M，我将对函数的下限和上限(即 M)进行二分查找。复杂度:O(NlogM)，因为对于每个 O(logM)，我计算 O(N) 的成本。

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

这个问题在规范中并不是很清楚(或者至少我是这么认为的)，因为当我第一次阅读它时，我不认为成本是根据所有供应点计算的，而只是从最近的供应点计算的。该示例清除了这一点。另外，我不知道我对成本(位置)函数是凸函数的假设是否真的正确。但我已经尝试了很多例子，似乎是这样。

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

Answer 1

列表中两个连续供应商位置之间的最小目标值必须出现在两个供应商位置之一。要看到这一点，请考虑两个供应商位置，中间没有供应商位置，它们的位置相差超过 1。假设左侧供应商位置给出的目标值小于或等于右侧供应商位置。然后，每次您从左侧供应商位置向右移动 1 步时，目标函数都会上升(微弱地，它可能会保持不变)，因为目标函数的变化量与您向右移动 1 步时的变化量相同两个连续供应商位置之间的时间。因此，您唯一需要计算的是有多少供应商位置提供相同的全局最小值。这些将出现在连续的段中(供应商位置给出的端点)，并且每个段的端点之间的所有位置也将给出相同的全局最小值。

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

通过从左到右处理，可以在 O(N) 时间内为 N 个供应商计算每个供应商位置的目标值。