微软面试100题（32题）：交换元素求最小差值

有两个序列a,b，大小都为n,序列元素的值任意整数，无序；

要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。

例如:   

var a=[100,99,98,1,2, 3];

var b=[1, 2, 3, 4,5,40];

这个题目的原型是之前做过的ACM动态规划

多米诺骨牌（DOMINO）

问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：

顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

这里改变下输入， a中的第i个元素和b中的第i个元素，构成第i组，所以输入为一个二维数组input[][2]

int input[][2] = { {100,1}, {99 ,2 } , {88, 3}, {1,4}, {2,5}, {3,40}};

可以使用一个二维数组，x为当前的组序号，y为这组能达到的差的值，其值为反转的次数。

那么可以预见，这是个稀疏矩阵，为了节省空间，采取三元组来存储。

使用三元组记录结果

typedef struct tagLoc{

int x, y;

char rev;

} Loc;

x记录到目前的处理的组的序号。

y记录计算出的上下两组之间的差。

rev记录要达到这组值翻转的次数。

声明一个大数组Loc all[1000],记录所有的可能性。

当x=0时，

如果不翻转0组，那么有y = 99， rev = 0

如果翻转0组，那么有y=-99, rev =1。

当x=n的时候，

遍历数组all中x=n-1的元素,即上一组的所有可能的值。

对于每个可能值 all[m] (all[m].x = n-1)

如果不翻转n组，那么有 x = n, y = all[m].y +  （input[i][0]-input[i][1]） , rev = all[m].rev

如果翻转第n组，那么有 x = n, y = all[m].y -  （input[i][0]-input[i][1]） , rev = all[m].rev+1

完成所有组后，对于最后一组x= 6,

all中的元素，当x=6时，y的绝对值最小的时候即经过rev次反转上下两组的最小差

/*
 * =====================================================================================
 *
 *       Filename:  domino.c
 *
 *    Description:  DP domino
 *
 *        Version:  1.0
 *        Created:  10/02/2012 06:16:15 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>

#include <stdio.h>

#define MAX (1<<32)-1;


int revcount;
int mindis;


typedef struct tagLoc{
    int x, y;
    char rev;
} Loc;
int LocSize = 0;
Loc* all;

int input[][2] = { {100,1}, {99 ,2 } , {88, 3}, {1,4}, {2,5}, {3,40}};
void domino(){
    int i = 1;
    for(; i< 6; i++){
        revcount = 0;
        mindis = (1<<32)-1;

        int steps = input[i][0]-input[i][1];
        int loci = 0;
        int tLocSize = LocSize;
        for(;loci<tLocSize; loci++){
            if(all[loci].x == i-1){
                int tmpdis;
                all[LocSize].x = i;
                all[LocSize].y = all[loci].y+steps;
                all[LocSize].rev = all[loci].rev;

                all[LocSize].y > 0? (tmpdis = all[LocSize].y): (tmpdis = 0-all[LocSize].y);
                if(tmpdis<=mindis){
                    mindis = tmpdis;
                    if(revcount>all[LocSize].rev) revcount = all[LocSize].rev;
                }
                LocSize++;

                all[LocSize].x = i;
                all[LocSize].y = all[loci].y - steps;
                all[LocSize].rev = all[loci].rev+1;
                all[LocSize].y > 0? (tmpdis = all[LocSize].y): (tmpdis = 0-all[LocSize].y);
                if(tmpdis<mindis){
                    mindis = tmpdis;
                    revcount = all[LocSize].rev;
                }
                LocSize++;
            }
        }

    }
}



/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{

    all = (Loc *)malloc(10000*sizeof(Loc));
    all[0].x = 0;
    all[0].y = 99;
    all[0].rev = 0;
    all[1].x=0;
    all[1].y=-99;
    all[1].rev = 1;
    LocSize= 2;
    domino();
    int i = 0;
    for(;i<LocSize; i++){
        printf ( "%d: x:%d, y %d rev:%d\n",i,all[i].x, all[i].y, all[i].rev );
    }
    printf ( "min distance: %d, reverse time: %d\n",mindis, revcount );
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */