题目描述：
给定你一个整数数组 nums
我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。
如果可以完成则返回true ， 否则返回 false 。
注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。
数据范围：
$1 \le nums.len \le 30; 0 \le nums[i] \le 10^4$
题解：
假设 $A$ 数组的和为 $s_1$ ，则 $\frac{s_1}{k} = \frac{s}{n - k}$ ，可以得到 $s_1 = \frac{sum}{n}\times k$ 。也就是 $s_1$ 等于平均值乘以数量。
动态规划：
使用动态规划算法，从 $n$ 中取出 $k$ 个数，看能否凑出 $s_1$ 。如果没有取出个数的限制，就可以直接使用可行性背包判断能否凑出来 $s_1$ 。但是存在个数限制，可以把个数也设计成状态。
原可行性背包问题 $dp[i][j]$ 表示从前 $i$ 个物品中取出一些物品，能否装满 $j$ 容量的背包。这里需要加上个数状态，即 $dp[i][k][j]$ 表示从前 $i$ 个物品中取出 $k$ 个，是否能装满 $j$ 。
原状态转移方程为 dp[i][j] = dp[i][j] | dp[i-1][j - nums[i]]。可以优化为一维 dp[j] |= dp[j - nums[i]]， $j$ 需要从后往前遍历。
加了状态 $k$ 之后的状态转移方程 d[i][k][j] = dp[i][k][j] | dp[i-1][k-1][j - nums[i]]。优化为一维 dp[k][j] = dp[k][j] | dp[k-1][j - nums[i]]， $j$ 需要从后往前遍历， $k \in [1, n]$ ，但是需要遍历 $i \in [0, n], j \in [0, sum], k\in[1, n)$ ，复杂度比较高。
状态压缩优化：
因为 $n$ 的范围非常小，所以可以使用状态压缩，使用一个整数的每一位 $0/1$ 来表示一维空间。具体可以使用 $dp[j]$ 的第 $i$ 位 $0/1$ 表示 $dp[i][j]$ 的值。然后转移的时候 dp[i][j] = dp[i][j] | dp[i - 1][j - nums[i]] 可以变为 dp[j] = dp[j] | (dp[j - nums[i]] << 1)，需要左移一位。
折半查找+二进制枚举：
因为 $s_1 = \frac{sum}{n} \times k$ ，考虑每个数都减去平均值，那么目标就是找出一个子序列和为 $0$ 。但是由于平均值可能为小数，所以直接将平均值扩大 $n$ 倍，也就是将里面的每个数扩大 $n$ 倍。 $x = x \times n - sum$ ，目标就是从找出一个子序列和为 $0$ 。可以直接使用二进制枚举枚举子序列，但是复杂度比较高，复杂度为 $2^{30} \approx 10^9$ 。可以考虑将数组分为两半枚举，先枚举左半边，如果出现为 $0$ 的直接返回 true。否则的话记录一下枚举出来的值，存起来。然后枚举右半边，如果出现了为 $0$ 直接返回 true。如果在左边找到了当前和的相反数也可以直接返回。但是需要注意的是不能全选了，全选了 $B$ 就没了。可以特判一下，是否是满状态。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool splitArraySameAverage(vector<int> &nums)
{
int sum = 0;
int n = nums.size();
for (auto &x : nums)
sum += x;
vector<vector<int>> dp(n + 1, vector<int>(sum + 1));
dp[0][0] = true;
for (int i = 0; i < n; ++i)
{
for (int j = sum; j >= nums[i]; --j)
{
for (int k = 1; k <= n; ++k)
{
dp[k][j] = dp[k][j] | dp[k - 1][j - nums[i]];
}
}
}
for (int i = 1; i < n; ++i)
{
if (sum * i % n == 0 && dp[i][sum * i / n])
{
return true;
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool splitArraySameAverage(vector<int> &nums)
{
int sum = 0;
int n = nums.size();
for (auto &x : nums)
sum += x;
vector<int> dp(sum + 1);
dp[0] = 1;
for (int i = 0; i < n; ++i)
{
for (int j = sum; j >= nums[i]; --j)
{
dp[j] |= (dp[j - nums[i]] << 1);
}
}
for (int i = 1; i < n; ++i)
{
if (sum * i % n == 0 && (dp[sum * i / n] >> i) & 1)
{
return true;
}
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool splitArraySameAverage(vector<int> &nums)
{
int sum = 0;
int n = nums.size();
if(n == 1) return false;
for (auto &x : nums)
sum += x;
for (auto &x : nums)
x = x * n - sum;
int m = n >> 1;
unordered_set<int> s;
for (int i = 1; i < (1 << m); ++i)
{
int tmp = 0;
for (int j = 0; j < m; ++j)
{
if ((i >> j) & 1)
tmp += nums[j];
}
if (tmp == 0)
return true;
s.insert(tmp);
}
for (int i = 1; i < (1 << (n - m)); ++i)
{
int tmp = 0;
for (int j = m; j < n; ++j)
{
if ((i >> (j - m)) & 1)
tmp += nums[j];
}
if (tmp == 0)
return true;
if (s.count(-tmp) && i != (1 << (n - m)) - 1)
return true;
}
return false;
}
};
|