Readme

2171.Removing-Minimum-Number-of-Magic-Beans

本题的关键是我们要有直觉，最终所有袋子的统一的豆子数目，一定等于原始袋子里某一袋的数目。这可以用反证法说明。我们将所有的豆子按照从大到小的顺序排列，假设最优解对应的最终每袋豆子数是k，介于beans[i]和beans[i+1]之间，那么我们必然要把第i+1袋到最后一袋的豆子都拿走，同时将前i袋里每袋豆子都降至数目k。显然，这不会是最优解，因为我们如果将答案k上调为为beans[i]，依然把第i+1袋到最后一袋的豆子都拿走，但前i袋豆子需要拿走的数目会变少。所以最终的k一定是某个beans[i]。

我们将beans从大到小排列之后，可以遍历一遍每个beans[i]查验如果它是最终解，那么需要移动的豆子总数包括两部分：前i袋需要移走sum[0:i] - beans[i]*(i+1)，后i袋需要全部拿走sum[i+1:n-1]。因此本题就是寻找sum[0:n-1] - beans[i]*(i+1)全局最小值所对应的i。