最小不兼容性

题目

1681. 最小不兼容性

---

给你一个整数数组 nums​​​ 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。

一个子集的 不兼容性 是该子集里面最大值和最小值的差。

请你返回将数组分成 k 个子集后，各子集 不兼容性 的 和 的 最小值 ，如果无法分成分成 k 个子集，返回 -1 。

子集的定义是数组中一些数字的集合，对数字顺序没有要求。

示例 1：

输入：nums = [1,2,1,4], k = 2
输出：4
解释：最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和，但是第一个集合有 2 个相同的元素，所以不可行。

示例 2：

输入：nums = [6,3,8,1,3,1,2,2], k = 4
输出：6
解释：最优的子集分配为 [1,2]，[2,3]，[6,8] 和 [1,3] 。
不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。

示例 3：

输入：nums = [5,3,3,6,3,3], k = 3
输出：-1
解释：没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。

提示：

• 1 <= k <= nums.length <= 16
• nums.length 能被 k 整除。
• 1 <= nums[i] <= nums.length

题解

方法一：

思路

状压dp

定义$f_s$为nums中选取下标集合为s的最小不兼容性。s用一个二进制数表示集合，二进制的第i位为1代表选取nums[i]。

例如nums = [1,2,1,4]，$f_{1}0=2$，这是因为$10=(1010{)}_2$，低位若从0开始，我们选取低位第2和第3位，得到$f_{10}=nums[3]-nums[0]=3$

我们的状态转移可以从小集合向大集合转移。

假设对于集合s，比其小的集合t，状态$f_t$均已求出。

那么我们只需枚举s的合法子集u（合法子集就是u的大小为n/k且u对于nums中不能有重复的数），并求出u中最大的nums值$m{x}_u$以及最小值$m{n}_u$,然后$f_{s-u}+m{x}_u-m{n}_u$的最大值便是$f_s$。

以这个思路实现了一份代码，不幸的是超时了。

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> f(1<<n, INF);
        f[0] = 0;
        for (int i=1; i<1<<n; i++) {
            for (int j=i; j!=0; j = (j-1)&i) {
                int bc = 0, ok = 1, pre=-1, mx=-1, mn=20;
                for (int c=0; c<n; c++) {
                    if (j>>c&1) {
                        bc++;
                        mx = max(mx, nums[c]);
                        mn = min(mn, nums[c]);
                        if (pre == nums[c]) ok = 0;
                        else pre = nums[c];
                    }
                }
                if (ok && bc == n/k) f[i] = min(f[i], f[i^j]+mx-mn);
            }
        }
        // for (int i=0; i<1<<n; i++) {
        //     cout << i << " " << f[i] << "\n";
        // }
        return f[(1<<n)-1] == INF ? -1 : f[(1<<n)-1];
    }
};

现在分析这份代码的时间复杂度。

我们从小到大地枚举了$[1,2^n)$内的数，我们将这些数视为二进制数，则可以认为是按照大小从小到大的枚举了集合。保证了在求大集合的状态时，其子集状态均已求出。

随后我们使用了二进制的技巧实现了枚举当前集合i的子集j。

for (int j=i; j!=0; j = (j-1)&i) {
    // j is subset 
}

然后又花了$O(n)$时间检查子集是否合法，并求出集合中的最大/最小值。

我们换一种思路来分析外两层循环的时间复杂度。

在$[1,2^n)$中有只含1个1的二进制数有n个；只含两个1的二进制数有$(\genfrac{}{}{0ex}{}{n}{2})$个；只含i个1的二进制数有$(\genfrac{}{}{0ex}{}{n}{i})$个;

对于含i个1的二进制数其子集的个数又有$2^i$个。根据二项式定理，外层两层循环次数$\sum _{i=0}^n{2}^i(\genfrac{}{}{0ex}{}{n}{i})=(2+1{)}^n$

再记上内层循环，时间复杂度为$O(n{3}^n)$。

考虑如何优化这份代码，实际上可以预处理出所有大小为n/k且不含重复数字的合法子集以及它们的最大值和最小值。预处理的时间是$O(n{2}^n)$，但之后的只需$O(1)$便可判断子集是否合法以及获取最大/最小值。那么总时间复杂度就降到了$O(3^n)$。可以通过本题。

代码

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int bit_cnt(int x) {
        int rt = 0;
        while (x) {
            rt++;
            x &= (x-1);
        }
        return rt;
    }
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> ok(1<<n, 1); // 满足集合大小为n/k，且无重复
        vector<int> mx(1<<n, -1); // 满足集合中最大值
        vector<int> mn(1<<n, 20); // 满足集合中最小值
        for (int i=0; i<1<<n; i++) {
            if (bit_cnt(i) != n/k) {
                ok[i] = 0;
                continue;
            }
            int pre = -1;
            for (int j=0; j<n; j++) {
                if (i>>j&1) {
                    if (pre == nums[j]) {
                        ok[i] = 0;
                        break;
                    } 
                    mx[i] = max(mx[i], nums[j]);
                    mn[i] = min(mn[i], nums[j]);
                    pre = nums[j];
                }
            }
        }

        vector<int> f(1<<n, INF);
        f[0] = 0;
        for (int i=1; i<1<<n; i++) {
            for (int j=i; j!=0; j = (j-1)&i) {
                if (ok[j]) f[i] = min(f[i], f[i^j]+mx[j]-mn[j]);
            }
        }
        // for (int i=0; i<1<<n; i++) {
        //     cout << i << " " << f[i] << "\n";
        // }
        return f[(1<<n)-1] == INF ? -1 : f[(1<<n)-1];
    }
};