chandu-and-his-toy-stack

After setting up the area. Chandu wanted all his toys to be stacked there in that area. So that all of them are accessible easily. Currently, He is having N stacks of toys each with height H_1,H_2...H_n (assuming all toys are of same height).Chandu did not like the configuration much and want to change the height of each stack. To increase the height of a particular stack he can add some toys to it and to decrease the height he can take out some toys from that stack. 
Chandu, knows that he requires X units of effort for putting up an item onto the stack and Y units of effort for removing it.
Help, chandu in setting up his toys.

Input:

First Line of input contains an integer t, which is the number of test cases. then, t lines follow where first line of each test case contains three integers N, X and Y then N lines follow containing two integers each a[i] and b[i] (Initial height of i\;th stack and final height of i\;th stack.)

Output:

Output an integer which is the minimum effort required.

NOTE:  he just need to make stacks of given height. Not necessarily each stack should be made from its corresponding stack. 

Constraints:

1 ≤ t ≤ 100,  
1 ≤ N ≤ 10^5,  
1 ≤ a[i],b[i] ≤ 10^6

SAMPLE INPUT
1
3 6 4
3 1
1 2
1 2

SAMPLE OUTPUT
10

Explanation

Here, He is having 3 stacks initially of height 3,1 and 1
He can take out one toy from first stack to get a stack with two toys with 4 units of effort.
He can put toy on second stack to get a stack with two toys with 6 units of effort.
Total effort = 10 units.
After the two operations he will have three stacks with required heights.

Source: hackerearth | Difficulty: EASY
Tags: Data structures

Greedy algorithms


Solutions:
def naive(n, x, y, initial, required):
	initial = sorted(initial)
	required = sorted(required)
	#print n, x, y
	#print initial
	#print required
	answer = 0
	for a, b in zip(initial, required):
		if a != b:
			if a > b:
			  answer += ((a-b) * y)
			else:
				answer += ((b-a) * x)
	return answer


if __name__ == "__main__":
	t = eval(input())
	for _ in range(t):
		n = eval(input())
		x = eval(input())
		y = eval(input())
		#n, x, y = map(int, raw_input().strip().split())
		initial = [0] * n
		required = [0] * n
		for i in range(n):
			a, b = list(map(int ,input().strip().split()))
			initial[i] = a
			required[i] = b
		print(naive(n, x, y, initial, required))


t=int(input())
while(t):
	t=t-1
	n=int(input())
	x=int(input())
	y=int(input())
	a=[]
	b=[]
	while(n):
		n=n-1
		num=input().split()
		a.append(int(num[0]))
		b.append(int(num[1]))
	a.sort()
	b.sort()
	work=0
	for i in range(0,len(a)):
		if(a[i]>b[i]):
			work+=(a[i]-b[i])*y
		elif(a[i]<b[i]):
			work+=(b[i]-a[i])*x
	print(work)


test = int(input())
while test:
	N = int(input())
	X = int(input())
	Y = int(input())
	initial, final = [], []
	for i in range(N):
		a, b = list(map(int,input().split()))
		initial.append(a)
		final.append(b)
	initial = sorted(initial)
	final = sorted(final)
	effort = 0
	for i in range(N):
		if initial[i] > final[i]:
			temp = initial[i] - final[i]
			effort += temp * Y
		elif initial[i] < final[i]:
			temp = final[i] - initial[i]
			effort += temp * X
	print(effort)
	
	test -= 1