【算法】Maximum Split of Positive Even Integers 拆分成最多数目的正偶数之和 -上篇贪心模拟-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Maximum Split of Positive Even Integers 拆分成最多数目的正偶数之和 -上篇贪心模拟。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Maximum Split of Positive Even Integers 拆分成最多数目的正偶数之和

问题描述：

给你一个整数 finalSum 。请你将它拆分成若干个互不相同的正偶数之和，且拆分出来的正偶数数目最多。

比方说，给你 finalSum = 12 ，那么这些拆分是符合要求的（互不相同的正偶数且和为 finalSum）：(2 + 10) ，(2 + 4 + 6) 和 (4 + 8) 。它们中，(2 + 4 + 6) 包含最多数目的整数。注意 finalSum 不能拆分成 (2 + 2 + 4 + 4) ，因为拆分出来的整数必须互不相同。
请你返回一个整数数组，表示将整数拆分成最多数目的正偶数数组。如果没有办法将 finalSum 进行拆分，请你返回一个空数组。你可以按任意顺序返回这些整数。

$1 <= finalSum <= 10^{10}$

分析

很多题解上来就是贪心的具体操作，作为菜鸡的我，贪心一直不是我的首选。

贪心算法作为一种算法思路，有的人说很简单，有的人说很难。因为贪心算法本身并不存在一种固定的模式，它往往是以局部的最优解，从而得到整体的最优解的思路。
但是有些情况下，局部的最优解，并不能保证整体的最优，这种场景下，贪心就不行了。
所以使用贪心算法解决问题，对问题的分析力，有比较高的要求。

首先问题要将num拆成偶数之和，如果可以拆分，那么num必须是even。
因为要求最终的结果中偶数不能重复使用，而且拆分的偶数要最多。
把可能的偶数全部列出来 $2,4,6,8...2^{34}$
$\log_2(10^{10})\approx33.21$

要从34个数中，选择k个组成num，最长的k，问题就可以解决了。

最简单暴力的方式就是枚举选择的方案数,因为每个元素只能用一次，那么方案数就等于 $2^n$ ，上限大概 $10^{10}$ .
这个数据规模，暴力是走不通的，但是思路没问题，毕竟一切恐惧源于火力不足。

暴力之所以耗时太多，还是由于计算了非常多的无效组合，但是只要时间给够，最终也是能出结果的。

暴力走不通，就想到了二分，二分同样也会走到暴力的上，在n个数字中找k个恰好等于num，此外由于k不一定连续，二分也没法用。

能想到的方法，由于时间复杂度不能用，二分也不行。就只能找找规律了。

因为num是偶数，那么它一开始一定可以拆成2个偶数x,y。比如[2,0],[2,2],但是要求必须是正偶数，且不相等。
所以num如果是2，或者4，就无法继续拆了，又或者num拆出了2，a,b,c，与x,假设x比较大如果继续拆，会与已经拆出的数产生重复，那么x就不能拆了。

特点1：为了拆出最多的偶数，那么较小的偶数就应该占多数。

那么就从最小的偶数2开始拆。
num=2,只能拆成2，
num=4,只能拆成4。
num=6,只能拆成2，4。
num=8,只能拆成2，6，当拆出2时，还有6，如果拆4，就重复了，只能不动，长度为2。
num=10,先拆2，余8，此时8继续拆成4，不行，拆6也不行，所以8也不能再拆了，所以只能是2,8，长度2.

num=12，先拆2，余10，再拆4，余6，此时再拆就是6，可以不动，长度3。

似乎这个思路得到的方案，不会有其他比它更优秀的方案了。

所以通过循环模拟这个过程。

代码

public List<Long> maximumEvenSplit(long finalSum) {
        List<Long> res = new ArrayList<>();
        if (finalSum % 2 == 1) return res;
        for (long i = 2; i <= finalSum; i += 2) {
            finalSum -= i;
            if(finalSum <=i) i+=finalSum;
            res.add(i);
        }
        if (finalSum!=0);
        return res;
    }