题目描述

Alex is given n piles of boxes of equal or unequal heights. In one step. Alex can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height

样例

n = 3;
boxinpiles = [5, 2, 1]

In the first step, remove 3 boxes from boxinpiles[0], and the new array is boxinpiles = [2,2,1] 
Now reduce the two taller piles by 1 box each to match the height of the shortest plle This takes 
2 steps because each step is performed on only one pile. The final number of steps requlred is 3    

排序

(排序 + 贪心) $O(nlog(n))$

从大到小排序，每一次找到当前值和下一个值的差距，从开始到当前值都需要减去这个差距才可以和下一个值

的高度保持一致，因此直接遍历累加答案即可

C++ 代码

int pilesOfBox(int n, vector<int> &piles)
{
    sort(piles.begin(), piles.end(), greater<int>());
    int ans = 0;
    for(int i = 0; i + 1 < piles.size(); i++)
    {
        int gap =  piles[i] - piles[i + 1];
        ans += gap * (i + 1);
    }
    return ans;
}