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

Problem - E - Codeforces

題意：
給 N 種球的個數 A[]。要求按照下列規則將其分箱：
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).

解法：
首先注意，每個箱子都只有某一定種分箱方式，可以用比較少的球數描述。
考慮球數最少的那箱，令這箱球數為 x。那麼，考慮用 [ 1, x ] 個箱子去裝，最少球數會是：

這裡至多有 x^0.5 種最少球數，而當箱子數量超過 x^0.5 時，由於最多的最少球數不超過 x^0.5，所以 x 球分箱的最少球數至多只有 2 * x^0.5 種。由於只要有最少球數，就能推得答案，所以枚舉 2 * x^0.5 種最少球數即可。 記得要判掉不可裝箱的情況。

時間 / 空間複雜度：
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;
}