Tuesday, August 26, 2008

Linking two arrays

Q: given
A1,A2,....Am
B1,B2,....Bn

All of them are positive integers.

find a way to link B to A so that the sum of absolute difference of each B and its assigned A is minimized. prove your method is right.

Two case (1) m=n (2) m>n

A: (1) m = n
a. sort A and B in increasing order, so that A1'<=A2'<=...<=Am', and B1'<=B2'<=...<=Bn';
b. link B1' to A1', B2' to A2', ..., and Bn' to Am';

(2) m>n
?

No comments: