最小化 (firstA 的最大值 - firstA 的最小值) + (secondB 的最大值 - secondB 的最小值)

Question

给定n对整数，将它们分成两个子集A和B，以使得（子集A中第一个值的最大差值与子集B中第二个值的最大差值之和）最小。

示例：n = 4 {0, 0}; {5;5}; {1; 1}; {3; 4}

A = {{0; 0}; {1; 1}} B = {{5; 5}; {3; 4}} (maximum difference among first values of A, maximum difference among second values of B).

(子集A中第一个值的最大差值) = fA_max-fA_min=1-0=1 (子集B中第二个值的最大差值) = sB_max-sB_min=5-4=1 因此，答案为1+1=2，并且这是最好的方法。

显然，值之间的最大差值等于（最大值-最小值）。所以，我们需要做的是找出 (fA_max-fA_min)+(sB_max-sB_min) 的最小值。

假设给定的数组为arr[]， arr[].first 表示第一个值，arr[].second 表示第二个值。

我认为在二次复杂度下解决这个问题非常容易。只需要按照第一个值进行排序。然后，子集A中的所有元素应该依次从排序数组中选取。因此，您可以遍历所有排序后的范围[L;R]。对于每个范围，尝试将该范围内的所有元素添加到子集A中，并将所有剩余元素添加到子集B中。 更详细的信息，请看这是我的C++代码：

int calc(pair<int, int> a[], int n){
    int m = 1e9, M = -1e9, res = 2e9; //m and M are min and max of all the first values in subset A 
    for (int l = 1; l <= n; l++){
        int g = m, G = M; //g and G are min and max of all the second values in subset B
        for(int r = n; r >= l; r--) {
            if (r - l + 1 < n){
                res = min(res, a[r].first - a[l].first + G - g);
            }
            g = min(g, a[r].second);
            G = max(G, a[r].second);
        }
        m = min(m, a[l].second);
        M = max(M, a[l].second);
    }
    return res;
}

---

现在，我想将我的算法优化为loglinear复杂度。当然，首先将数组按第一个值排序。之后，如果我固定fA_min = a[i].first，那么如果索引i增加，fA_max将增加，而（sB_max - sB_min）会减少。

但现在我还是卡在这里了，有没有什么方法可以在loglinear复杂度下解决这个问题呢？

- Minh Hien

---

请提供一两个示例数据，这将有所帮助。 - chux - Reinstate Monica

计算排序数组的所有连续子集的结果是正确的方法，我同意。为此，您需要n^2，然后对于每个结果集_b的最小值和最大值，需要另外n个（在那里我认为您的代码不起作用）。因此O(n^3)。通过保存set_b的相关索引，可以避免第三个循环。 动态程序也可以减少前两个循环。 - Luka

1. 看起来 n >= 4，集合A的子集大小应该为2或更大，集合B的子集大小也应该为2或更大，因为子集大小小于2没有意义。对吗？
2. 子集大小是否必须相等，或者一个子集大小为2，另一个子集大小为99都可以？
3. a[r].first - a[l].first 的溢出是否会造成问题？
4. 所有值都是非负数吗？
5. 为什么所有的int数学计算却在返回时将res提升为long long？

- chux - Reinstate Monica

这个问题的几何视角是：我们在欧几里得平面上有一组点，希望用两个无限长条带的联合体覆盖它们（这个联合体的形状类似于加号“+”），一个是垂直的，一个是水平的，并使它们的宽度之和最小化。 - David Eisenstat

有人考虑过线段树或其他数据结构吗？我正在尝试采用以下方法：循环n个max_first(A)的值，然后对于每个max_first(A)，在O(log(n))的时间内找到min(-min_first(A)+max_second(B)-min_second(B))。 - Minh Hien

Answer 1

以下方法是试图避免n^2的方法，使用 argmin 列表作为元组的第二个元素（假设是y部分）。其中点按照x排序。

一个观察是，有一个最佳解决方案，其中A包含索引argmin[0]或argmin[n-1]或两者都包含。

1. 在get_best_interval_min_max中，我们一次关注包括argmin[0]和y上下文中的下一个最小元素。然后我们从最大元素开始相同。

我们得到两个字典{(i，j)：(profit，idx)}，告诉我们在将points [i：j + 1]包含在A中时我们在y中获得了多少利润，对于y的最小值或最大值向前推进。 idx是argmin数组中的索引。

2. 假设max/min或y不在A中，计算每个dict的目标。

3. 合并两个字典的结果：(i1，j1)：(v1，idx1)和(i2，j2)：(v2，idx2)。结果：j2-i1+max_y-min_y-v1-v2。

约束条件：idx1 < idx2。因为argmin数组中的索引不能相交，否则y中的某些利润可能会计算两次。

平均而言，字典（dmin，dmax）比n小，但在x和y相关时最坏情况下[(i，i)for i in range(n)]它们正好是n，我们不节省任何时间。无论如何，在随机实例上，这种方法都要快得多。也许有人可以改进这一点。

import numpy as np
from random import randrange
import time

def get_best_interval_min_max(points):# sorted input according to x dim 
    L = len(points)
    argmin_b = np.argsort([p[1] for p in points])
    b_min,b_max = points[argmin_b[0]][1], points[argmin_b[L-1]][1]
    
    arg = [argmin_b[0],argmin_b[0]]
    res_min = dict()
    for i in range(1,L):
        res_min[tuple(arg)] = points[argmin_b[i]][1] - points[argmin_b[0]][1],i # the profit in b towards min
        if arg[0] > argmin_b[i]: arg[0]=argmin_b[i]
        elif arg[1] < argmin_b[i]: arg[1]=argmin_b[i]
        
    arg = [argmin_b[L-1],argmin_b[L-1]]
    res_max = dict()
    for i in range(L-2,-1,-1):
        res_max[tuple(arg)] = points[argmin_b[L-1]][1]-points[argmin_b[i]][1],i # the profit in b towards max
        if arg[0]>argmin_b[i]: arg[0]=argmin_b[i]
        elif arg[1]<argmin_b[i]: arg[1]=argmin_b[i]
    # return the two dicts, difference along y,     
    return res_min, res_max, b_max-b_min

def argmin_algo(points):
    # return the objective value, sets A and B, and the interval for A in points. 
    points.sort()
    # get the profits for different intervals on the sorted array for max and min
    dmin, dmax, y_diff = get_best_interval_min_max(points)
    key = [None,None]
    res_min = 2e9
    # the best result when only the min/max b value is includes in A
    for d in [dmin,dmax]:
        for k,(v,i) in d.items():
            res = points[k[1]][0]-points[k[0]][0] + y_diff - v
            if res < res_min: 
                key = k
                res_min = res

    # combine the results for max and min. 
    for k1,(v1,i) in dmin.items():
        for k2,(v2,j) in dmax.items():
            if i > j: break # their argmin_b indices can not intersect!
            idx_l, idx_h = min(k1[0], k2[0]), max(k1[1],k2[1]) # get index low and idx hight for combination
            res = points[idx_h][0]-points[idx_l][0] -v1 -v2 + y_diff
            if res < res_min: 
                key = (idx_l, idx_h) # new merged interval
                res_min = res
    return res_min, points[key[0]:key[1]+1], points[:key[0]]+points[key[1]+1:], key

def quadratic_algorithm(points):
    points.sort()
    m, M, res = 1e9, -1e9, 2e9
    idx = (0,0)
    for l in range(len(points)):
        g, G = m, M 
        for r in range(len(points)-1,l-1,-1):
            if r-l+1 < len(points):
                res_n = points[r][0] - points[l][0] + G - g
                if res_n < res:
                    res = res_n
                    idx = (l,r)
            g = min(g, points[r][1])
            G = max(G, points[r][1])
        m = min(m, points[l][1])
        M = max(M, points[l][1])
    return res, points[idx[0]:idx[1]+1], points[:idx[0]]+points[idx[1]+1:], idx

# let's try it and compare running times to the quadratic_algorithm
# get some "random" points
c1=0
c2=0
for i in range(100):
    points = [(randrange(100), randrange(100)) for i in range(1,200)]
    points.sort() # sorted for x dimention
    s = time.time()
    r1 = argmin_algo(points)
    e1 = time.time()
    r2 = quadratic_algorithm(points)
    e2 = time.time()
    c1 += (e1-s)
    c2 += (e2-e1)
    if not r1[0] == r2[0]:
        print(r1,r2)
        raise Exception("Error, results are not equal")
print("time of argmin_algo", c1, "time of quadratic_algorithm",c2)

- Luka

Answer 2

更新：@Luka证明了本答案中描述的算法并不精确。但我仍将其保留在此，因为它是一个很好的性能启发式，并为许多概率方法开辟了道路。

---

我将描述一个对数线性算法。我找不到反例。但我也找不到证明 :/

让集合A按第一个元素排序，集合B按第二个元素排序。它们最初是空的。从你的点集中取floor(n/2)个随机点放入集合A中。将剩余的点放入集合B中。将其定义为一个分区。

如果您无法将集合A的元素放入B并减少目标函数，或者无法将集合B的元素放入A并减少目标函数，则称分区为稳定的。否则，我们将称该分区为不稳定的。

对于不稳定的分区，唯一有趣的移动是将A的第一个或最后一个元素移动到B，或将B的第一个或最后一个元素移动到A。因此，我们可以在O(1)中找到给定不稳定分区的所有有趣移动。如果有趣的移动减少了目标函数，请执行它。这样做直到分区变得稳定。我猜想，分区变得稳定最多需要O(n)次移动。我还猜想，在分区变得稳定的时刻，您将拥有一个解决方案。

- joaopfg

---

我怀疑存在反例，并且可以通过实现此算法并将其与可证明的算法在小的随机实例上进行比较来找到它。 - David Eisenstat

@DavidEisenstat，您能解释一下您认为这个算法有问题的直觉吗？就我而言，我会尝试在小的随机实例上实现它并与暴力算法进行比较。 - joaopfg

我明白了。我的担忧也是它会陷入局部最优解。但很难想到一个反例。我会听从你的建议，尝试让计算机找到反例。 - joaopfg

这是一个不错的算法，考虑两个集合分别为： A: (0,0), (8,10), (9,10), (10,5) ==> diff=10 B: (11,11), (9,11), (20,20) ==> diff=9 你不能移动任何元素，但最佳解决方案应该是： A: (0,0) ==> diff=0 B: (10,5),(8,10), (9,10), ,(11,11), (9,11), (20,20) ==> diff=15 - Luka

我认为几何视角很有用，也许一些几何的论证可以改进n^2。 - Luka