介绍一种求差最小的整数数组划分方法

hongtianyu

题目描述
     一个整数数组A，取下标为i到j的部分，现需将将其划分成两部分PA、PB(不能对数组任何元素做位置调整)，使得|Sum(PA) - Sum(PB) |最小。
算法介绍
     令 S(i ) = A[0] + A[1] + ... + A  
     则 |Sum(PA) - Sum(PB) | = | (A + A[i+1] + ... + A[k]) - ( A[k+1] + .. + A[j] ) |  = | S(k) - S(i-1)  - ( S(j) - S(k) )  | = | S(j)  - 2S(k) + S(i-1) |
     只有求出使得| S(j)  - 2S(k) + S(i-1) |最小的k.
     策略：从数组的左边元素，和数组的右边元素向中间推进，推进的间隔变量设为g, g初始值设为1，左边元素下标变量设为l，右边元素标量设为r, 令 b = S(i-1), E = S(j),
     如果 ( E - 2*sumArr[l] + b  > 0 && E-2*sumArr[r]+b < 0 )，说明r > l, 且K 位于[l,r]，则倍增g，然后继续推进；
     如果 ( E - 2*sumArr[l] + b < 0 )，说明 k位于[l-g,l]，则使g减半，然后在新区间内推进；
     如果( E - 2*sumArr[r] + b > 0 )，说明 k 位于[r, r+g]，则使g减半，然后在新区间内推进；
     当推进区间只有两个元素和或者一个元素，则直接找出k.

注：算法有点类似于二分查找，时间复杂度为O(n).

代码
可以用递归或者循环实现，本人采用循环方式。由于要多次用到求和，与其一次次求，还不如预先一次求好，用数组存放起来。接口sumAll实现了这一过程。实现代码如下

typedef vector<int> ivector;

static int ABS( int a)
{
        return a > 0 ? a:-a;
}

static void sumAll( const ivector& arr,ivector& sumArr )
{
        sumArr.resize( arr.size() );
        sumArr[0] = 0;
        for( size_t i=0; i<arr.size(); ++i )
                sumArr = ( i>0 ? sumArr[i-1]:0) + arr;
}

        /**
        * find the partition k,making part A(k in A) and B.
        * the result of |SUM-A - SUM-B | must be the minimum.
        *@param        i  the left position in sumArr
        *@param        j  the right position in SumArr
        *@param        sumArr    the array of elements'sum,
        *                                  the ith element is the sum of the front n elements in original array.
        */
int minimize(int i,int j, ivector& sumArr)
{
        int l = i;
        int r = j;
        int g = 1;
        int b = i > 0 ? sumArr[i-1]:0;
        int E = sumArr[j];
        while( r - l > 1 )
        {
                l = l + g;
                r = r - g;
                if( E - 2*sumArr[l] + b  > 0
                        && E-2*sumArr[r]+b < 0 )
                {
                        g *= 2;
                        continue;
                }
                if( E - 2*sumArr[l] + b < 0 )
                {
                        r = l;
                        l = l - g;
                        g /= 2;
                }
                else if( E - 2*sumArr[r] + b > 0 )
                {
                        l = r;
                        r = r + g;
                        g /= 2;
                }                        
        }
        return ABS(E - 2*sumArr[l] + b ) <= ABS(E - 2*sumArr[r] + b) ? l:r;

}

代码经过初步测试，大家有兴趣也可以测测。
注：以上算法思想来自于一篇ACM论文，本人用自己理解的方式把它实现了，如果有什么问题和改进，欢迎大家指出。

5毛党党员

贴代码 最好 选择插入程序代码

drowsyboy

我最近也用到了这个算法