### PROBLEM LINK:

**Editorialist**: Lalit Kundu

### DIFFICULTY:

CAKEWALK

### PRE-REQUISITES:

GREEDY, SORTING

### PROBLEM:

**K (<100)** students(each with height **A[i]**) to be assigned a total of **K**(each pencil of height **B[i]**) pencils. Each student is to be assigned one pencil. You want to give a pencil to each kid in a way such that the sum of the absolute differences of the height of a kid and the length of the pencil assigned to him/her is minimized. What is the minimum sum of absolute differences that can be achieved?

### EXPLANATION:

Greedily, we think like which pencil should we give to the kid with smallest height: intuitively the pencil with smallest height. We can do this continuously until we have assigned pencils to all the kids.

What we have done above is equivalent to:

Sort both the arrays **A** and **B**. Now, assign pencil with height **B[i]** to the kid with height **A[i]** ie. add to answer **abs(A[i]-B[i])** for each **i=1** to **N**.

#### Proof:

Let’s say we have an arbitrary arrangement:

**kid _{1} → pencil_{p1}**

**kid**

_{2}→ pencil_{p2}.

.

.

**kid**.

_{N}→ pencil_{pN}Here, kids are in increasing order, but pencils are not. So, to improve this arrangement we need to decrease the number of inversions in **p1,p2 … pN**.

For example if **kid_7 → pencil_6** and **kid_11 → pencil_4**, then this is an inversion, since 7 < 11 and 6 > 4. We will change this to **kid_7 → pencil_4** and **kid_11 → pencil_6**.

Say **a1 = |kid_7 - pencil_6| + |kid_11 - pencil_4|** and **b1 = |kid_7 - pencil_4| + |kid_11 - pencil_6|**. Prove yourselves that **b1 ≤ a1**. Hence, decreasing the number of inversions helps us in decreasing the answer. So, the array with 0 inversions will give optimal answer.