题目描述
给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中,使得同一个子集里面没有两个相同的元素。
一个子集的 不兼容性 是该子集里面最大值和最小值的差。
请你返回将数组分成 k 个子集后,各子集 不兼容性 的 和 的 最小值 ,如果无法分成分成 k 个子集,返回 -1 。
子集的定义是数组中一些数字的集合,对数字顺序没有要求。
样例
输入:nums = [1,2,1,4], k = 2
输出:4
解释:最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和,但是第一个集合有 2 个相同的元素,所以不可行。
输入:nums = [5,3,3,6,3,3], k = 3
输出:-1
解释:没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。
思路
先是想办法搜索,发现搜索过程是在划分子集
先选出一个子集,再从剩下没选的集合里再选一个子集
考虑预处理出每个子集的价值,看了看数据范围
好的我们可以用二进制枚举枚举出所有符合划分条件的子集。
二进制表示当前子集所选的个数,1表示选0表示不选。1的个数要等于一个组的大小,同时判断组里是否有相同元素
可以用一个数组记录
vector<int> a(1 << n, -1);
为什么要把数组初始化位-1?
在考虑到k == nums.size()时,合法子集的价值是0,如果默认初始化位0这样再选取子集的时候不知道该子集的价值是0还是不合法。(好伤心在这里wa了30min,还好lc可以看到错误样例,不然一个小时可能都想不到);
如果使用unordered_map的话倒是可以看set中是否有该元素判断
预处理完了,接下来就是考虑该怎么选了。
二进制还是很容易往dp想,状态压缩
状态表示和预处理时一样,dp[i]的值表示当前状态的最小代价,dp[0] = 0,其他无穷。
考虑如何遍历剩下没选的元素的全部子集,在预处理中合法的进行状态转移
if(~a[sub]) dp[i | sub] = min(dp[i | sub], dp[i] + a[sub]);
如何遍历子集呢?OI-Wiki
code
class Solution {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
int n = nums.size();
int m = n / k;
vector<int> a(1 << n, -1);
vector<int> dp((1 << n), INT_MAX);
dp[0] = 0;
for (int i = 1; i < (1 << n); i++) {
if (__builtin_popcount(i) != m) continue;
int mn = 20, mx = 0;
unordered_set<int> cur;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
if (cur.count(nums[j]) > 0) break;
cur.insert(nums[j]);
mn = min(mn, nums[j]);
mx = max(mx, nums[j]);
}
}
if (cur.size() == m) a[i] = mx - mn;
}
for(int i = 0; i < 1 << n; i++)
{
if(dp[i] == INT_MAX) continue;
unordered_map<int, int> mp;
for (int j = 0; j < n; j++)
if (!(i & (1 << j))) mp[nums[j]] = j;
if(mp.size() < m) continue;
int x = 0;
for(auto& b : mp) x |= (1 << b.second);
for (int sub = x; sub; sub = (sub - 1) & x) {
if(~a[sub]) dp[i | sub] = min(dp[i | sub], dp[i] + a[sub]);
}
}
return dp[(1 << n) - 1] < INT_MAX ? dp[(1 << n) - 1] : -1;
}
};
讨厌状压,呕