#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

Source

信奥星OJ http://127.0.0.1