Question: A global distribution company has a stack of many items in its warehouse. Each stack is stored in the form of piles. The height of some ples is very high, and the height of some piles is very low and this unevenness is causing problems in the warehouse. To solve this, the company has developed a robot which will help in arranging all the piles property. To do it the company has prepared a list of N piles which contains the total number of items in each pile, each pile in the text has been identified by a unique to ranging from 0 to (N-1). The robot will go through this list first and then remove the items from the piles in such a manner that after removing all the items, the difference between the total items of any two piles is at most K. The robot can also remove a pile completely or left a pile complimely untouched if a pile has been removed completely than that pile will automatically get deleted from the list and will not be used in farther calculation.
Werse an algorithm for the robot to calculate how many items it will remove in seal from the piles
Input: The first line of the input consists of an integer — totalPiles, representing total number of piles in the warehouse(N). The secondline of the input consists of N space seperated integers representing the total number of items in each pile The thirdline of the input consists of an Integer- represents maximum difference between any two piles(K).
Sample testcase input:
4
3 1 5 1
2
output:
2
My idea: Every time we have two choices either remove the smallest element or subtract the excessive items wrt the minimum. Can some one help me with the idea or psuedo code?
Thanking you in Advance.
Bro it's called a "problem" not a "question"!!!!
Sorry for my poor choice of words;). Can you please help with the idea??
What are the limits on N and the sizes of piles?
1<=totalpiles<=10^6
1<=totalitem0,totalitem1...<=10^6
0<=difference<=10^6
Also, just to clarify, if I completely remove a pile, say pile $$$i$$$, then which of the following must hold:
first one
Wait I think I misunderstood initially -- we have to have this property for all pairs of (nonempty) piles? (I initially thought it would only be for adjacent piles xD)
OK, if the property must hold between all pairs of piles, not only adjacent ones, I think this is a solution.
Suppose first we sort the sizes of the piles (the property doesn't care about the order of the piles so we can do this. Suppose the sizes are $$$v[1] ... v[N]$$$. Now suppose that we fix the size of the smallest pile that we will have after we finish our operations, say it's $$$v[i]$$$. Then we must do the following
Now let $$$f(i)$$$ be the index of the smallest item that is greater than $$$v[i] + \textit{maximumDifference}$$$. All values of $$$f(i)$$$ can be computed in linear time by the 2-pointers technique, or in linearithmic time by binary search. For some fixed $$$i$$$ by the previous discussion the result will be
$$$ \sum_{j=1}^{i-1} v[i] + \sum_{j = f(i)}^n (v[j] - (v[i] + \textit{maximumDifference})) $$$
=
$$$ (f(i) - n + 1) (\textit{maximumDifference} - v[i])) + \sum_{j=1}^{i-1} v[i] + \sum_{j = f(i)}^n v[j] $$$
=
$$$ (f(i) - n + 1) (\textit{maximumDifference} - v[i])) + (v[1] + ... + v[n]) - (v[i] + ... + v[f(i) - 1]). $$$
And this can be calculated using, say, partial sums.