解决 ACM TJU 2886 - 餐厅
Solving ACM TJU 2886 - Restaurants
我正在尝试解决这个问题：http://acm.tju.edu.cn/toj/showp2886.html
我已经尝试了一些解决方案，我将解释其中的两个。请注意，两者都假设成本（位置）是一个凸函数，这意味着它向中间减少（实际上它在某个地方朝向中位数（供应点）），并且该图看起来或多或少像一个 U 形。
求cost(position) <= M的最左边和最右边补给点位置，找到最小值和最大值后，试试看能不能把区间调大一点（因为餐厅不必正好位于供应点上）。这是一个很好的解决方案，但需要非常多的时间来计算最后一位。它在 M 非常大且几乎没有最低成本的供应点的测试中失败。复杂度：O(NlogN) + O(M)。下面的解决方案超出了时间限制，但我尝试了另一个解决方案，我在 O(1) 中计算我可以在两个方向上走多少，但我得到了错误的答案。
由于函数是凸函数，我可以使用三元搜索来找到最小值。如果最小值小于 M，我将对函数的下限和上限（即 M）进行二分查找。复杂度：O(NlogM) 因为对于每个 O(logM) 我计算 O(N) 的成本。
这是我尝试过的方法，但我仍然得到 "Wrong Answer"，所以我需要一些帮助，因为这让我抓狂。
这个问题在规格上并不是很清楚（或者至少我是这么认为的），因为当我第一次阅读它时，我认为成本不是从所有供应点计算的，而是从最近的供应点计算的。该示例清除了这一点。
另外，我不知道我对成本（位置）函数是凸函数的假设是否真的正确。但我试过很多例子，似乎是这样。
谢谢。任何帮助表示赞赏。 :D
列表中两个连续供应商位置之间的最小 objective 值必须出现在两个供应商位置之一。要看到这一点，请考虑两个供应商位置，中间没有供应商位置，它们的位置相差超过 1。假设左侧供应商位置给出的值小于或等于 objective 值，而不是右侧供应商位置。然后，每次您从左侧供应商位置开始向右移动 1 步时，objective 函数都会上升（微弱地，它可能会保持不变），因为 objective 函数的变化量与您相同在两个连续的供应商位置之间一次向右移动 1 步。因此，您唯一需要计算的是有多少供应商位置提供相同的全局最小值。这些将出现在连续的段中（供应商位置给出的端点），每个段端点之间的所有位置也将给出相同的全局最小值。
请注意，根据我的分析，有可能有两个非连续段给出相同的全局最小值 objective 值。如果是这样，那么你的函数可能不是凸的，这可能是你目前尝试的困难来源。
通过从左到右处理，可以在 O(N) 时间内为 N 个供应商计算每个供应商位置的 objective 值。
我正在尝试解决这个问题：http://acm.tju.edu.cn/toj/showp2886.html
我已经尝试了一些解决方案，我将解释其中的两个。请注意，两者都假设成本（位置）是一个凸函数，这意味着它向中间减少（实际上它在某个地方朝向中位数（供应点）），并且该图看起来或多或少像一个 U 形。
求cost(position) <= M的最左边和最右边补给点位置，找到最小值和最大值后，试试看能不能把区间调大一点（因为餐厅不必正好位于供应点上）。这是一个很好的解决方案，但需要非常多的时间来计算最后一位。它在 M 非常大且几乎没有最低成本的供应点的测试中失败。复杂度：O(NlogN) + O(M)。下面的解决方案超出了时间限制，但我尝试了另一个解决方案，我在 O(1) 中计算我可以在两个方向上走多少，但我得到了错误的答案。
由于函数是凸函数，我可以使用三元搜索来找到最小值。如果最小值小于 M，我将对函数的下限和上限（即 M）进行二分查找。复杂度：O(NlogM) 因为对于每个 O(logM) 我计算 O(N) 的成本。
这是我尝试过的方法，但我仍然得到 "Wrong Answer"，所以我需要一些帮助，因为这让我抓狂。
这个问题在规格上并不是很清楚（或者至少我是这么认为的），因为当我第一次阅读它时，我认为成本不是从所有供应点计算的，而是从最近的供应点计算的。该示例清除了这一点。 另外，我不知道我对成本（位置）函数是凸函数的假设是否真的正确。但我试过很多例子，似乎是这样。
谢谢。任何帮助表示赞赏。 :D
列表中两个连续供应商位置之间的最小 objective 值必须出现在两个供应商位置之一。要看到这一点，请考虑两个供应商位置，中间没有供应商位置，它们的位置相差超过 1。假设左侧供应商位置给出的值小于或等于 objective 值，而不是右侧供应商位置。然后，每次您从左侧供应商位置开始向右移动 1 步时，objective 函数都会上升（微弱地，它可能会保持不变），因为 objective 函数的变化量与您相同在两个连续的供应商位置之间一次向右移动 1 步。因此，您唯一需要计算的是有多少供应商位置提供相同的全局最小值。这些将出现在连续的段中（供应商位置给出的端点），每个段端点之间的所有位置也将给出相同的全局最小值。
请注意，根据我的分析，有可能有两个非连续段给出相同的全局最小值 objective 值。如果是这样，那么你的函数可能不是凸的，这可能是你目前尝试的困难来源。
通过从左到右处理，可以在 O(N) 时间内为 N 个供应商计算每个供应商位置的 objective 值。