【动态规划】【数学】【C++算法】805 数组的均值分割

本文介绍: 给定你一个整数数组 nums我们要将 nums 数组中的每个元素移动到 A 数组或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。如果可以完成则返回true ，否则返回 false 。注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。

【动态规划】【数学】【C++算法】18赛车

动态规划数学

给定你一个整数数组 nums
我们要将 nums 数组中的每个元素移动到 A 数组或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。
如果可以完成则返回true ，否则返回 false 。
注意：对于数组 arr , average(arr) 是 arr 的所有元素的和除以 arr 长度。
示例 1:
输入: nums = [1,2,3,4,5,6,7,8]
输出: true
解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
示例 2:
输入: nums = [3,1]
输出: false
参数范围:
1 <= nums.length <= 30
0 <= nums[i] <= 10⁴

令n=nums.length half=n/2。不失一般性，令A的长度小于等于B，则lena的长度取值范围[1,half]，lenb=n-lena。
数组A的和为：Sum

int GCD(int n1, int n2)
{
	int t1 = min(n1, n2);
	int t2 = max(n1, n2);
	if (0 == t1)
	{
		return t2;
	}
	return GCD(t2 % t1, t1);
}

class Solution {
public:
	bool splitArraySameAverage(vector<int>& nums) {
		const int n = nums.size();
		const int half = n / 2;
		vector<unordered_set<int>> vLeft(1), vRight(1);		
		CountToTotal( vLeft, nums.data(),0, half);
		CountToTotal(vRight, nums.data()+half, 0, n-half);

		const int total = std::accumulate(nums.begin(), nums.end(),0);
		for (int i = 1; i <= half; i++)
		{
			const int iGCD = GCD(i, n);
			if (0 != total % (n / iGCD))
			{
				continue;//A的和必定为整数
			}
			const int totalA = total * i / n;
			for (int j = 0; j <= i; j++)
			{// A数组总共选择i个，其中从左边选择j个
				for (const auto& iLeft : vLeft[j])
				{
					if (vRight[i - j].count(totalA - iLeft))
					{
						return true;
					}
				}
			}
		}
		return false;
	}
	void CountToTotal(std::vector<std::unordered_set<int>>& v, const int* p,int left,int r)
	{
		v[0].emplace(0);
		for (int i = left; i < r ; i++)
		{
			v.emplace_back();
			for (int j = v.size() - 1; j >= 1; j--)
			{
				for (const auto& pre : v[j - 1])
				{
					v[j].emplace(pre + p[i]);
				}
			}
		}
	}
};

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<int> nums;
	{
		Solution sln;
		nums = { 1,2,3,4,5,6,7,8 };
		auto res = sln.splitArraySameAverage(nums);
		Assert(true, res);
	}
	{
		Solution sln;
		nums = { 3,1};
		auto res = sln.splitArraySameAverage(nums);
		Assert(false, res);
	}
	{
		Solution sln;
		nums = { 18,10,5,3 };
		auto res = sln.splitArraySameAverage(nums);
		Assert(false, res);
	}
	
}

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛