求实现公平分包装所需添加的最少糖果数

给定数组arr，其中arr[i]代表第i种糖果的数量。需将所有糖果装入至少2个包装，要求每个包装内同类型糖果的数量相等。若当前糖果无法直接满足分配要求，可添加糖果，计算所需添加的最少糖果数。

示例：

• 输入arr = [1, 3, 4]：添加[1, 1, 0]颗糖果后得到[2, 4, 4]，可分成2个包装，每个包装的糖果分布为[1, 2, 2]，共添加2颗。
• 输入arr = [3, 3, 3, 3, 2]：仅需给最后一种糖果添加1颗，得到[3,3,3,3,3]，可分成3个或5个包装，满足要求。

现有暴力解法代码如下：

int mx = *max_element(arr.begin(), arr.end());
int mn = 1e9;
for (int sz = 2; sz <= mx; sz++) {
    int cnt = 0;
    for (int &x: arr) cnt += (sz - (x % sz)) % sz;
    mn = min(mn, cnt);
}
cout << mn << endl;

该解法遍历所有可能的包装数sz（从2到数组最大值），计算每种sz下需要添加的糖果总数，取最小值。但暴力法效率较低，尝试用质数优化后提升有限，询问是否存在更优解法。

核心逻辑不变：找到整数k≥2，使得所有糖果类型调整为k的倍数时，添加的糖果总数最小（总数公式为sum( (k - x%k) %k )）。优化点在于缩小需要遍历的k的范围，避免暴力遍历所有可能值。

关键观察 #

最优的k必然满足以下两种情况之一：

1. k是数组中某个元素x的因数：此时该类型糖果无需添加，直接能被k整除。
2. k是数组中某个元素x+1的因数：此时该类型糖果只需添加1颗即可被k整除，是成本极低的调整。

若某个k不满足上述两种情况，那么至少有一个类型的糖果需要添加≥2颗才能被k整除，此时大概率存在另一个候选k'能让总添加数更小。

优化步骤 #

1. 生成候选k集合：
   • 遍历数组中每个元素x，找出x的所有≥2的因数，加入集合（去重）。
   • 遍历数组中每个元素x，找出x+1的所有≥2的因数，加入集合（去重）。
2. 计算候选k的添加成本：
   • 对集合中的每个k，代入公式计算总添加糖果数。
3. 取最小值：
   • 所有候选k对应的总添加数中的最小值，即为答案。

实现代码示例 #

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <iostream>

using namespace std;

unordered_set<int> get_factors(int n) {
    unordered_set<int> factors;
    if (n < 2) return factors;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            factors.insert(i);
            factors.insert(n / i);
        }
    }
    factors.insert(n);
    return factors;
}

int min_add_candies(vector<int>& arr) {
    unordered_set<int> candidates;
    int mx = *max_element(arr.begin(), arr.end());
    
    for (int x : arr) {
        // 添加x的因数
        auto f1 = get_factors(x);
        for (int k : f1) candidates.insert(k);
        // 添加x+1的因数
        auto f2 = get_factors(x + 1);
        for (int k : f2) candidates.insert(k);
    }
    
    // 确保不遗漏2到mx之间的小值（可选，实际上述步骤已覆盖多数最优情况）
    for (int k = 2; k <= min(mx, 100); ++k) {
        candidates.insert(k);
    }
    
    int min_cnt = INT_MAX;
    for (int k : candidates) {
        int cnt = 0;
        for (int x : arr) {
            cnt += (k - (x % k)) % k;
        }
        if (cnt < min_cnt) {
            min_cnt = cnt;
        }
    }
    return min_cnt;
}

int main() {
    vector<int> arr1 = {1,3,4};
    cout << min_add_candies(arr1) << endl; // 输出2
    
    vector<int> arr2 = {3,3,3,3,2};
    cout << min_add_candies(arr2) << endl; // 输出1
    return 0;
}

效率对比 #

• 暴力法时间复杂度：O(m * n)，其中m是数组最大值，n是数组长度。当m很大（如1e6）时，效率极低。
• 优化后时间复杂度：O(n * sqrt(x) + c * n)，其中x是数组元素的最大值，c是候选k的数量（通常远小于m），效率提升显著。

内容的提问来源于stack exchange，提问作者Vedanta Mohapatra