求 f(x) = a*min(b, x) 形式函数最大值的算法？
Algorithm for finding max value of functions of the form f(x) = a*min(b, x)?
我有一个元组数组 (a, b)，其中 a > 0 和 b > 0。
每个元组代表一个函数 f 使得 f(x, a, b) = a * min(b, x).
是否有针对给定 x 的已知算法来查找哪个元组 returns 最大值？
我不想评估每个函数来检查最大值，因为我会针对不同的 x.
查询任意次数的数组
示例：
array = [ (1, 10), (2, 3) ]
x < 6 -> choose (2, 3)
x = 6 (intersection point) -> either (1, 10) or (2, 3) doesn't matter
x > 6 -> choose (1, 10)
所以问题是这些元组可以按 a 或 b 排序。但是它们之间可以有很多交点（如果我们将它们可视化为图形）。所以我想避免任何 O(n^2) 排序算法来检查 x 的某些范围，这是最好的功能。我的意思是我不想将每个函数与所有其他函数进行比较以找出从哪个点 x'（交点）以及我应该选择一个而不是另一个。
我认为你应该先根据 'b' 对数组进行排序，然后再根据 'a' 对数组进行排序。现在对于每个 x 只需使用二进制搜索并找到 min(b,x) 将根据值仅给出 b 或 x 的位置。因此，从那时起，如果 x 很小，那么 b 的所有即将到来的值然后将元组作为 t1 并且您可以使用该函数计算值，并且对于 b 的值将小于 x 您强制需要遍历。我不确定，但这是我能想到的。
效率的关键是避免无用的工作。如果您想象一棵决策树，p运行ing branches 是一个经常用于此的术语。
对于您的情况，决策是基于在两个函数（或参数元组）之间进行选择。为了 select 这两个函数中的任何一个，您只需确定它们为您提供相同值时的值 x。其中之一对较小的值表现更好，一个对较大的值表现更好。另外，不要忘记这部分，可能一个函数 always 比另一个函数执行得更好。在这种情况下，性能较差的可以完全删除（另见上文，避免无用的工作！）。
使用这种方法，您可以从这个切换点映射到左边的功能。找到任意值的最优函数只需要找到下一个更高的切换点。
顺便说一句：确保你有适当的单元测试。这些东西很复杂，尤其是浮点值和舍入误差，所以你想确保你可以 运行 一套不断增长的测试，以确保一个小错误修复不会破坏其他地方。
数据经过预处理后，可以及时计算出这个最大值O(log(n))，其中n是元组的个数(a, b)。
首先，我们来看一个稍微简单一点的问题：你有一个对(c, b)的列表，你想找到c的最大值，条件是b<=x，并且您想针对 x 的不同值多次执行此操作。例如下面的列表：
c b
------
11 16
8 12
2 6
7 9
6 13
4 5
有了这个列表，如果用x=10查询，c的可用值有2、7、4，最大为7。
让我们按 b:
对列表进行排序
c b
------
4 5
2 6
7 9
8 12
6 13
11 16
当然，这个列表中的某些值永远无法给出答案。例如，我们永远不能在答案中使用 b=2、c=6 行，因为如果 6<=x 那么 5<=x，那么我们可以使用 c=4 行来得到更好的答案。所以我们不妨去掉列表中的那些对，即所有 c 的值到目前为止不是最高的对。所以我们将列表缩减为：
c b
------
4 5
7 9
8 12
11 16
鉴于此列表，索引在 b，很容易找到 c 的最大值。您所要做的就是在列表中找到 b 的最高值 <=x，然后 return 对应 c.
的值
显然，如果您更改问题以便只需要带有 b>=x 的值（而不是 b<=x），您可以做完全相同的事情。
对。那么这对您提出的问题有何帮助？
对于给定的 x 值，您可以将问题拆分为 2 个问题。如果您能回答这两个问题，那么您就可以回答整个问题：
- 在
(a, b) 和 b<=x 的配对中，哪一个的 f(x,a,b) = a*b 值最高？
- 在
(a, b) 和 b>=x 的配对中，哪一个的 f(x,a,b) = a*x 值最高？
对于 (1)，简单地让每对 c=a*b 然后完成上面概述的整个索引繁琐。
对于 (2)，让 c=a 并执行上面的索引操作，但转过来执行 b>=x 而不是 b<=x；当您得到 a 的答案时，不要忘记将它乘以 x。
假设 a、b 和查询的 x 总是非负的，每个查询可以在 O(log(n)) 时间后完成 O(n*log(n)) 预处理步骤：
预处理步骤消除了这种被其他人严格控制的功能。例如，对于每个 x，(5, 10) 都大于 (1, 1)。 （所以，如果数组中有 (5, 10)，那么我们可以删除 (1, 1)，因为它永远不会是任何 x 的最大值。）
这是一般条件：当且仅当 c > a 和 (c*d > a*b) 时，对于每个 x，函数 (a, b) 大于 (c, d)。 （这很容易证明。）
现在，我们要做的是删除这样的函数 (a, b)，其中存在 (c, d) 使得 c > a 和 (c*d > a*b)。这可以在 O(n*log(n)) 时间内完成：
1 - 按字典顺序对元组进行排序。我所说的按字典顺序是先比较它们的第一个坐标，如果它们相等，则比较第二个。例如，排序数组可能如下所示：
(1, 5)
(1, 17)
(2, 9)
(4, 3)
(4, 4)
2 - 以相反的顺序遍历已排序的数组，并跟踪您目前遇到的 a*b 的最大值。我们称此值为 M。现在，假设我们在循环中处理的元素是 (a, b)。如果 a*b < M，我们删除这个元素。因为我们之前处理的一些(c, d)，c > a和c*d > a*b都没有，所以(a, b)是没用的。这一步之后，示例数组将变为：
(2, 9)
(4, 4)
(4, 3)因为被(4, 4)支配而被删除。 (1, 17) 和 (1, 5) 被删除，因为它们被 (2, 9) 支配。
一旦我们去掉所有对任何 x 都不是最大值的函数，剩余函数的图形将看起来像 this。
如图所示，每个函数都是从与前一个相交点到与后一个相交点的最大值。对于上面的示例，(4, 4) 和 (2, 9) 相交于 x = 8。所以 (4, 4) 是 x = 8 之前的最大值，在那之后，(2, 9) 是最大值。
我们要计算数组中连续函数相交的点，以便对于给定的 x，我们可以对这些点进行二进制搜索以找到哪个函数 returns 最大值。
我有一个元组数组 (a, b)，其中 a > 0 和 b > 0。
每个元组代表一个函数 f 使得 f(x, a, b) = a * min(b, x).
是否有针对给定 x 的已知算法来查找哪个元组 returns 最大值？
我不想评估每个函数来检查最大值，因为我会针对不同的 x.
示例：
array = [ (1, 10), (2, 3) ]
x < 6 -> choose (2, 3)
x = 6 (intersection point) -> either (1, 10) or (2, 3) doesn't matter
x > 6 -> choose (1, 10)
所以问题是这些元组可以按 a 或 b 排序。但是它们之间可以有很多交点（如果我们将它们可视化为图形）。所以我想避免任何 O(n^2) 排序算法来检查 x 的某些范围，这是最好的功能。我的意思是我不想将每个函数与所有其他函数进行比较以找出从哪个点 x'（交点）以及我应该选择一个而不是另一个。
我认为你应该先根据 'b' 对数组进行排序，然后再根据 'a' 对数组进行排序。现在对于每个 x 只需使用二进制搜索并找到 min(b,x) 将根据值仅给出 b 或 x 的位置。因此，从那时起，如果 x 很小，那么 b 的所有即将到来的值然后将元组作为 t1 并且您可以使用该函数计算值，并且对于 b 的值将小于 x 您强制需要遍历。我不确定，但这是我能想到的。
效率的关键是避免无用的工作。如果您想象一棵决策树，p运行ing branches 是一个经常用于此的术语。
对于您的情况，决策是基于在两个函数（或参数元组）之间进行选择。为了 select 这两个函数中的任何一个，您只需确定它们为您提供相同值时的值 x。其中之一对较小的值表现更好，一个对较大的值表现更好。另外，不要忘记这部分，可能一个函数 always 比另一个函数执行得更好。在这种情况下，性能较差的可以完全删除（另见上文，避免无用的工作！）。
使用这种方法，您可以从这个切换点映射到左边的功能。找到任意值的最优函数只需要找到下一个更高的切换点。
顺便说一句：确保你有适当的单元测试。这些东西很复杂，尤其是浮点值和舍入误差，所以你想确保你可以 运行 一套不断增长的测试，以确保一个小错误修复不会破坏其他地方。
数据经过预处理后，可以及时计算出这个最大值O(log(n))，其中n是元组的个数(a, b)。
首先，我们来看一个稍微简单一点的问题：你有一个对(c, b)的列表，你想找到c的最大值，条件是b<=x，并且您想针对 x 的不同值多次执行此操作。例如下面的列表：
c b
------
11 16
8 12
2 6
7 9
6 13
4 5
有了这个列表，如果用x=10查询，c的可用值有2、7、4，最大为7。
让我们按 b:
c b
------
4 5
2 6
7 9
8 12
6 13
11 16
当然，这个列表中的某些值永远无法给出答案。例如，我们永远不能在答案中使用 b=2、c=6 行，因为如果 6<=x 那么 5<=x，那么我们可以使用 c=4 行来得到更好的答案。所以我们不妨去掉列表中的那些对，即所有 c 的值到目前为止不是最高的对。所以我们将列表缩减为：
c b
------
4 5
7 9
8 12
11 16
鉴于此列表，索引在 b，很容易找到 c 的最大值。您所要做的就是在列表中找到 b 的最高值 <=x，然后 return 对应 c.
显然，如果您更改问题以便只需要带有 b>=x 的值（而不是 b<=x），您可以做完全相同的事情。
对。那么这对您提出的问题有何帮助？
对于给定的 x 值，您可以将问题拆分为 2 个问题。如果您能回答这两个问题，那么您就可以回答整个问题：
- 在
(a, b)和b<=x的配对中，哪一个的f(x,a,b) = a*b值最高？ - 在
(a, b)和b>=x的配对中，哪一个的f(x,a,b) = a*x值最高？
对于 (1)，简单地让每对 c=a*b 然后完成上面概述的整个索引繁琐。
对于 (2)，让 c=a 并执行上面的索引操作，但转过来执行 b>=x 而不是 b<=x；当您得到 a 的答案时，不要忘记将它乘以 x。
假设 a、b 和查询的 x 总是非负的，每个查询可以在 O(log(n)) 时间后完成 O(n*log(n)) 预处理步骤：
预处理步骤消除了这种被其他人严格控制的功能。例如，对于每个 x，(5, 10) 都大于 (1, 1)。 （所以，如果数组中有 (5, 10)，那么我们可以删除 (1, 1)，因为它永远不会是任何 x 的最大值。）
这是一般条件：当且仅当 c > a 和 (c*d > a*b) 时，对于每个 x，函数 (a, b) 大于 (c, d)。 （这很容易证明。）
现在，我们要做的是删除这样的函数 (a, b)，其中存在 (c, d) 使得 c > a 和 (c*d > a*b)。这可以在 O(n*log(n)) 时间内完成：
1 - 按字典顺序对元组进行排序。我所说的按字典顺序是先比较它们的第一个坐标，如果它们相等，则比较第二个。例如，排序数组可能如下所示：
(1, 5)
(1, 17)
(2, 9)
(4, 3)
(4, 4)
2 - 以相反的顺序遍历已排序的数组，并跟踪您目前遇到的 a*b 的最大值。我们称此值为 M。现在，假设我们在循环中处理的元素是 (a, b)。如果 a*b < M，我们删除这个元素。因为我们之前处理的一些(c, d)，c > a和c*d > a*b都没有，所以(a, b)是没用的。这一步之后，示例数组将变为：
(2, 9)
(4, 4)
(4, 3)因为被(4, 4)支配而被删除。 (1, 17) 和 (1, 5) 被删除，因为它们被 (2, 9) 支配。
一旦我们去掉所有对任何 x 都不是最大值的函数，剩余函数的图形将看起来像 this。
如图所示，每个函数都是从与前一个相交点到与后一个相交点的最大值。对于上面的示例，(4, 4) 和 (2, 9) 相交于 x = 8。所以 (4, 4) 是 x = 8 之前的最大值，在那之后，(2, 9) 是最大值。
我们要计算数组中连续函数相交的点，以便对于给定的 x，我们可以对这些点进行二进制搜索以找到哪个函数 returns 最大值。