如何找到 Multiset-sum 中的第 K 个最小元素？
How To Find K-th Smallest Element in Multiset-sum?
需要一些帮助来设计算法来解决这个问题。
令a和b为a ≤ b 的整数，设 [a,b] 表示集合 {a, a + 1, a + 2, ..., b}。假设我们给定n这样的集合，[a1,b1],...[an,bn], 他们的多重集和是
S = {a1, a1 + 1,..., b1,a2,a2 + 1,...,b2,.. .,an,an + 1, ..., bn}
例如，[5,25]、[3,10]和[8,12]的多重集和是
{3,4,5,5,6,6,7,7,8,8,8,9,9,9,10,10,10,...,25}
给定集合[a1, b1],...,[an, bn] 使得 0 ≤ ai, bi ≤ N 和整数 k > 0，设计一个有效的算法，输出 S 中的 k 个最小元素，即集合的多集和。根据n和N确定算法的运行时间
我已经设计了两个名为 FindElementsBefore(x, [a1,b1]...[a n,bn]) 和 FindElementsAfter(x, [a1,b1]...[an,bn])。它们都接受元素 x 和每个集合，return S 中分别小于 x 和大于 x 的元素数。
我的教授告诉我，使用这两个辅助方法，我应该可以解决上述问题，但我完全被难住了。我该如何解决？
使用二进制搜索。
您已经知道多重集和中的最大值和最小值。因此，您有第 k 个最小元素的上限和下限。现在你可以根据 FindElementsBefore(mid, ...) <= k.
的值简单地递归上界和下界
需要一些帮助来设计算法来解决这个问题。
令a和b为a ≤ b 的整数，设 [a,b] 表示集合 {a, a + 1, a + 2, ..., b}。假设我们给定n这样的集合，[a1,b1],...[an,bn], 他们的多重集和是
S = {a1, a1 + 1,..., b1,a2,a2 + 1,...,b2,.. .,an,an + 1, ..., bn}
例如，[5,25]、[3,10]和[8,12]的多重集和是
{3,4,5,5,6,6,7,7,8,8,8,9,9,9,10,10,10,...,25}
给定集合[a1, b1],...,[an, bn] 使得 0 ≤ ai, bi ≤ N 和整数 k > 0，设计一个有效的算法，输出 S 中的 k 个最小元素，即集合的多集和。根据n和N确定算法的运行时间
我已经设计了两个名为 FindElementsBefore(x, [a1,b1]...[a n,bn]) 和 FindElementsAfter(x, [a1,b1]...[an,bn])。它们都接受元素 x 和每个集合，return S 中分别小于 x 和大于 x 的元素数。
我的教授告诉我，使用这两个辅助方法，我应该可以解决上述问题，但我完全被难住了。我该如何解决？
使用二进制搜索。
您已经知道多重集和中的最大值和最小值。因此，您有第 k 个最小元素的上限和下限。现在你可以根据 FindElementsBefore(mid, ...) <= k.