Amazon : Find minimum|a-b|+|b-c|+|c-a|

Given 3 arrays, pick 3 nos, one from each array, say a,b,c such that |a-b|+|b-c|+|c-a| is minimum，请给出解答的证明

我只能说这题从证明和程序的编写上远没有开始预料的那么简单

分情况讨论，考虑abc之间的大小关系，最多只有3！=6种
以a>b>c为例，则原式简化为a-b+b-c+a-c=2a-2c

只需取a中最大，c中最小即可。b甚至都不用检查（因为如果没有b在[a,c]之间的话，在其他的讨论中会获得更好的答案）

不知道对不对？

分情况讨论，考虑abc之间的大小关系，最多只有3！=6种
以a>b>c为例，则原式简化为a-b+b-c+a-c=2a-2c

只需取a中最大，c中最小即可。b甚至都不用检查（因为如果没有b在[a,c]之间的话，在其他的讨论中会获得更好的答案）

不知道对不对？
epic 发表于 2011-6-28 12:50

你这个时间复杂度岂不是n^2?

对三个数组排序，时间复杂度nlogn

做一个三路merge sort, 每次对A,B,C中最小的a,b,c三个数做判断，同时更新结果。
在a,b,c中取最小的数x, x进到下一个元素，这样新的3元素对就形成了。

这是解法，证明这个解法的正确性比较麻烦。同时要证明加入a == b < c, 那么是递增A数组还是B数组。
需要证明递增A,B可以，结果都是一样的。这套证明的关键就是你指出的|a-b|+|b-c|+|c-a| 只和最大最小的两个元素相关，和中间那个无关，每一个iteration唯一可以改良的办法就是递增最小元素所在的那个数组。

int CalcABS(int a, int b, int c)
{
        return abs(a-b) + abs(a-c) + abs(b-c);
}

int GetMin(vector<int>& vec)
{
        assert(!vec.empty());
       
        int nMin = vec[0];
        for (int i = 0; i < vec.size(); i++)
        {
                if (vec[i] < nMin)
                        nMin = vec[i];
        }

        return nMin;
}

int GetABC(int a[], int na, int b[], int nb, int c[], int nc, int& sa, int& sb, int& sc)
{
        assert(a && na>0 && b && nb>0 && c && nc>0);

        sort(a, a+na);
        sort(b, b+nb);
        sort(c, c+nc);

        int i = 0;
        int j = 0;
        int k = 0;
        sa = sb = sc = 0;

        int nMin = CalcABS(a[i], b[j], c[k]);
        while (i != na-1 || j != nb-1 || k != nc-1)
        {
                vector<int> vec;
                if (i != na-1) vec.push_back(a[i]);
                if (j != nb-1) vec.push_back(b[j]);
                if (k != nc-1) vec.push_back(c[k]);

                int nRes = GetMin(vec);

                if (i != na-1 && a[i] == nRes)
                        i++;
                else if (j != nb-1 && b[j] == nRes)
                        j++;
                else k++;

                nRes = CalcABS(a[i], b[j], c[k]);
                if (nRes < nMin)
                {
                        sa = a[i];
                        sb = b[j];
                        sc = c[k];
                        nMin = nRes;
                }
        }

        return nMin;
}