JZTXT

最小不兼容性

发布时间 2023-06-30 21:07:17作者: 失控D大白兔

给你一个整数数组 nums​​​ 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。
一个子集的不兼容性是该子集里面最大值和最小值的差。
请你返回将数组分成 k 个子集后，各子集 不兼容性的和的最小值 ，如果无法分成分成 k 个子集，返回 -1 。

1. 暴力枚举 + 动态规划

class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(1<<n,INT_MAX); //记录对应状态最小值
        int group = n/k;//每个集合数量

        //状态边界计算，计算只有一个组的不兼容性
        for(int mask=0;mask<(1<<n);mask++){//遍历所有状态
            if(__builtin_popcount(mask)!=group) continue;//剔除不满足条件的状态，这里只计算一组的不兼容性

            int mn = INT_MAX; int mx = INT_MIN;
            vector<bool> vis(n);
            int cnt = 0;
            for(int i=0;i<n;i++){//遍历每个数
                if(mask&(1<<i)){//如果该状态下该数存在
                    if(vis[nums[i]]) break; //该状态下存在重复数，跳出
                    vis[nums[i]] = true;//标记该数
                    //求该组的最大值和最小值
                    mn = min(mn,nums[i]);
                    mx = max(mx,nums[i]);
                    cnt++;//组中数加一
                }
            }
            if(cnt!=group)  continue;
            dp[mask] = mx - mn;//记录该状态的不兼容性
        }

        for(int mask=0;mask<(1<<n);mask++){//遍历所有状态
            if(dp[mask]==INT_MAX) continue;  //只从已经记录的状态转移计算下一个状态
            int sub = ((1<<n)-1)^mask; //求mask的补集
            for(int cur=sub;cur>0;cur = (cur-1)&sub)
                if(dp[cur]!=INT_MAX) dp[mask|cur] = min(dp[mask|cur],dp[mask] + dp[cur]);
        }
        return dp[(1<<n)-1]==INT_MAX?-1:dp[(1<<n)-1];
    }
};

2. 回溯 + 动态规划