I came through a question in which all the numbers in an array were supposed to be made equal minimising the total cost of operations.
operations:
a) Increase a number by 1, costs A.
b) Decrease a number by 1, costs B.
c) simultaneously decrease a number by 1 and increase another number by 1, costs C.
1<=array length<=500000
1<=A, B, C<=10000
0<=array numbers<=1000000000
What is the approach to solve this problem?
Can you provide some sample test cases?
n = int(input())
a, b, c = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
median = l[n//2]
left = 0
right = 0
for i in range(n):
if l[i] < median:
left += l[i]
elif l[i] > median:
right += l[i]
ans = left*a + right*b
minimum = min(left, right)
ans = min(ans, minimum*c + (left-minimum)*a + (right-minimum)*b)
print(ans)
In this code, I tried to make all elements equal to the median of the array, numbers less than median needs to be incremented and numbers greater than median need to be decremented. So either we can separately do increment with cost a and decrement with cost b or do both the operation with cost c and if there are any elements left then increment or decrement those elementes according to their need.
Can you give the link to the problem? I think I have a solution .
N=3
A=1
B=100
C=100
1 3 8
ans 12
N=3
A=100
B=1
C=100
1 3 8
ans 9
N=3
A=100
B=100
C=1
1 3 8
ans 4
These were the only testcase provided, the median method doesn’t work for the 3rd test case I think.
it was asked in a company coding test so I don’t have a link.
Okkk , Sort all the no.s , calculate prefix sum , trying making all elements equal to that element . Now I hope you know how to do the first two steps , for the third one , for each index i
Increments required is ( (i + 1) * val[ i ] - pre[i] )) , decrements required is (( total - pre[i]) - (( n-1-i ) * val[i])) , now let z= minimum of increment and decrements so now you just need to take minimum of ( increment * A + decrement *B , z*C + (increment - z)*A + (decrement - z)*B )
The mathematical statements is based on 0 based indexing
Free feel to ask doubts .
I have the same solution, but no proof it will work. I tried coming up with a formal proof, as some similar problems are solved this way, but the difference is that in the problems where we claim that some value already present in the array is optimal, the cost of increasing and decreasing is equal.
Do you have some kind of a formal proof of this?
just for clarity, by this method it is always true that the final value of all number must be one of the number in the array , is it so?..if so then
n=3
A=100
B=100
C=1
1 3 8
ans 4
will this work?..here the final value of the numbers are 4 4 4 in the array
Yes you are right 
and @nichke you too , maybe we can do binary search to find the element which will give us minimum answer , like I think there will be only one peak . Will have to think about the proof .