#P3325. 拿出最少数量的魔法豆
拿出最少数量的魔法豆
Description
给定一个正整数数组beans
,其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中拿出一些豆子(也可以不拿出),使得剩下的非空袋子中魔法豆的数目相等。一旦把魔法豆从袋子中取出,你不能再将它放到任何袋子中。
请设计一个程序计算若要是所有非空袋子的魔法豆数量相同,你需要拿出魔法豆的最少数目。
Input Format
第一行输入一个正整数n
,表示袋子数量。
第二行以此输入n
个正整数表示每个袋子中魔法豆的数量。
Output Format
输出一个正整数,表示满足题目要求时需要拿出豆子的最少数量。
4
4 1 6 5
4
Hint
解释:
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。剩下袋子中魔法豆的数目为:[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。剩下袋子中魔法豆的数目为:[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。剩下袋子中魔法豆的数目为:[4,0,4,4]总共拿出了 1 + 2 + 1 = 4 个魔法豆,剩下非空袋子中魔法豆的数目相等。没有比取出 4 个魔法豆更少的方案。
数据范围:
1 <= beans.length <= 105
1 <= beans[i] <= 105