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
?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment