# CFR 792 E. Colored Balls ( Math, Sqrt Decomposition )

Problem - E - Codeforces

1. 同一個箱子不能存在兩種球
2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1
3. 所有球都必須存在於一個箱子裡
4. 不得有空箱

The first line contains one integer number n (1 ≤ n ≤ 500).
The second line contains n integer numbers a1, a2, ... , an (1 ≤ ai ≤ 1e9).

O( maxa^0.5 * N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500;

int N;
int A[ MAXN ];

ll calc( int minv ){
if( minv == 0 ) return 1LL << 60;
ll res = 0;
for( int i = 0; i < N; ++i ){
int h = A[ i ] / ( minv + 1 );
int k = A[ i ] % ( minv + 1 );
if( k == 0 ){
res += h;
continue;
}
int f = minv - k;
if( h < f ) return 1LL << 60;
res += h + 1;
}
return res;
}

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
sort( A, A + N );
}
{
ll ans = 1LL << 60;
for( int i = 1; i * i <= A[ 0 ]; ++i ){
ans = min( ans, calc( i ) );
ans = min( ans, calc( A[ 0 ] / i ) );
ans = min( ans, calc( A[ 0 ] / i - 1 ) );
}
cout << ans << endl;
}
return 0;
}
```