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.

题意概述

有$n$个盒子，第$i$个盒子的大小为$a_i$。每次可以将一个盒子拆分成两个盒子满足拆分后盒子的大小之和等于拆分前盒子的大小。问至少拆分成多少个盒子使得最大盒子和最小盒子的大小之差不大于$1$。

数据范围：$0 \le n \le 500, \ 1 \le a_i \le 10^9$。

算法分析

设最小盒子的大小为$r$。根据贪心策略，$r$越大，盒子数越少。

如何判断$a_i=rx+(r+1)y$是否有自然数解呢？

因为$a_i=a_i/r \times r+a_i \bmod r$，所以可以先把$a_i$分解成$(a_i/r)$个$r$相加，再加上$a_i \bmod r$。如果$a_i \bmod r \le a_i/r$，那么我们就可以把剩下来的$a_i \bmod r$一个一个分配到前面$(a_i/r)$个$r$上，并且满足最大值和最小值之差小于等于$1$这个条件。否则，无论怎么分配都会使得最大值和最小值之差大于$1$。

这样我们就可以判断对于某一个$r$，是否所有盒子都能够被分解成若干个$r$和若干个$(r+1)$相加。

接下来的问题就是如何找到这个$r$。易知$1 \le r \le \min(a_i)$。可以发现，如果$\min(a_i)$很大，在$\sqrt{\min(a_i)}$到$\min(a_i)$中可能满足条件的$r$是很少的，而且它们都在$\min(a_i)/t \ (1 \le t \le \sqrt{\min(a_i)})$附近。事实上，我们只需要从$1$到$\sqrt{\min(a_i)}$枚举$k$，分别判断$k, \min(a_i)/k, \min(a_i)/k-1$是否满足条件，取最大值即可。

最后，如果求出了满足条件的$r$，那么每个盒子被拆分后至少有$(a_i-1)/(r+1)+1$个。

代码

#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;
}