Does the problem have a solution?

Question

Programming

There are two sequences of numbers:
a1, a2, a3… an
b1, b2,b3… bn
The arithmetic mean of these two sequences are equal.
The difference between the sequences is calculated as follows:
R = |a1-b1| + |a2-b2| + |a3-b3| +… + |an-bn|
The problem is whether it is possible to find such a coefficient k by multiplying the first sequence by which
so that the difference between the sequences is minimal.
those.
R = |k*a1-b1| + |k*a2-b2| + |k*a3-b3| +… + |k*an-bn|
those. we need to find a k such that R is minimal.
In other words, you need to choose such a scaling factor for the first sequence so that the difference between the sequences is minimal.
Of course, this problem is quite easily solved by "binary search" (up to a certain accuracy), but for this you need to perform a certain number of calculations R with different k.
Is it possible to somehow find this k not by enumeration?
UPD. All numbers >= 0

Answer 1

1. R = a1*|k-b1/a1| + a2*|k-b2/a2| + a3|k3-b3/a3| +… + an|k-bn/an| (if ai=0, then we don’t take it out of the brackets and we don’t care.
2. Obviously, such a function is piecewise linear with respect to k on each of the sections, k, for which the modules open with the same sign (assume that a1/b1>b2 /a2>...bn/an, if this is not the case, sort it so that it is.) This means that on the section [(ai/bi,(ai+1)/(bi+1)] the function will be linear (! !!This is generally not true for (-inf,+inf) 3.
Since it is linear, its minimum will be reached at one of the points ai/bi.
bi)
5. Profit
And no binary search ))

Answer 2

I may be wrong, but if the sequences do not have any functional dependency, then no, the only solution is brute force.

Answer 3

Binary search needs R(k) to be linear, and in your case, if I'm not mistaken, it can be anything.