# Colored Balls

## 题目描述

There are $n$ boxes with colored balls on the table. Colors are numbered from $1$ to $n$. $i$-th box contains $a_i$ balls, all of which have color $i$. You have to write a program that will divide all balls into sets such that:

• each ball belongs to exactly one of the sets,
• there are no empty sets,
• there is no set containing two (or more) balls of different colors (each set contains only balls of one color),
• there are no two sets such that the difference between their sizes is greater than $1$.

Print the minimum possible number of sets.

## 代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long n, m, r = 1, ans, a[501];
bool check(long long t) {
for (int i = 1; i <= n; ++i)
if (a[i] % t > a[i] / t) return false;
return true;
}
int main()
{
cin >> n;
m = 1e9;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
m = min(m, a[i]);
}
long long p = (long long) sqrt(m);
for (long long i = 1; i <= p; ++i) {
if (m / i > r && check(m / i)) r = m / i;
if (m / i - 1 > r && check(m / i - 1)) r = m / i - 1;
if (i > r && check(i)) r = i;
}
for (int i = 1; i <= n; ++i) {
ans += (a[i] - 1) / (r + 1) + 1;
}
cout << ans << endl;
return 0;
}


418 I'm a teapot