贪心法(III) 整数的分分合合
+++++++++++++++++++++++++++++++++++++++++++++++

这次讲两个与整数有关的贪心算法例子，分别是\ :strong:`找零问题`\ 和\ :strong:`整数最大拼接问题`\ 。

找零问题
^^^^^^^^^^^^^^^^

:strong:`找零问题`\ 是许多算法书中贪心算法的入门例题。找零问题看似很简单，但是实际上也大有玄机。

一个典型的找零问题大概是这样的，给出一套货币的所有面值，比如1元、5元、10元一共三种面值的纸币，数量不限。再给出一个要找零的金额，比如33元，要求出一个找零方案，所用的纸币数量最少。这个问题一看就很简单直接，一般用过钱的人都知道，尽量先挑面值大的就可以得到这个最优解，比如33元就可以是3张10元加3张1元，一共6张纸币，这就是最优解，没有比这数量更少的方法了。这种找零方法显然是一种典型的贪心法。

**找零问题的一般描述**

一套货币共有 :math:`n` 种面值，分别为正整数 :math:`c_1,c_2,\dots,c_n`\ ，其中 :math:`c_1=1`\ ，求一种使用货币数量最少的方法来组合出金额 :math:`a \ge 1`\ 。

根据生活经验，如果货币为人民币（不失一般性，暂不考虑角和分这两种货币单位），面值共有1元、2元、5元、10元、20元、50元、100元七种，只要使用如前所述的贪心法，从能使用的最大面额开始，每次都先选用最大面额的人民币，就可以得到最优解。

例如79元，按照这个贪心策略，先选用50元的人民币1张，剩余29元继续使用这个策略，先选20元的1张，然后剩余9元，先选5元的1张，最后剩4元就选用2元的2张，这样一共使用了1+1+1+2=5张，这就是最优解。

但是问题来了。首先，怎么证明对于人民币来说这个贪心策略是正确的？其次，是不是任意的面值组合都可以使用贪心法求解？

事实上并不是任何面值组合的货币都可以用贪心法来求解找零问题的。我们可以举一个反例，比如题目给出的货币面值为1元、5元和7元三种，这套奇怪的货币用贪心法就会失误。假设现在要找零的金额是11元，使用贪心法，先用最大面值的7元货币一张，剩余4元，再用四张1元的，得到贪心解一共需用5张货币。但是实际上最优解是用两张5元和一张1元，一共3张货币。

.. warning::

   有些货币面值的组合不能用贪心法求解找零问题，这样的问题只能用动态规划的方法来求解。

让人不快的是，任意给定一套货币，证明它是否适用贪心法的方法并不简单。不过一般我们可以依据经验和寻找反例来进行判断，大概可以有下面这么几条规则：

1. 真实世界在用的货币，比如人民币、美元等，一般都适用贪心法，即使只是取了其中一部分货币。例如著名的《算法导论》里的例题就使用了四种美元硬币：1美分、5美分、10美分和25美分，但它们也是可以用贪心法求解的。
2. 可以证明，货币的面值如果从1开始，构成等比数列 :math:`\{1,c,c^2,\dots,c^k\},(c\gt1,k\gt0)` 的，一定适用贪心法。在《算法导论》里有详细的证明，但是证明过程比较玄学，这里就不详细解释了，记住这个结论就好。
3. 如果和通常的真实货币面值不同，特别是有一些奇怪的数值，例如7、11等，又构不成等比数列的就要小心了。遇到这样的数值可以用下面的方法来找反例：

.. admonition:: 找零问题反例检查规则

   1、如果只有两种面值，那么问题一定可以用贪心法求解。

   2、如果面值超过两种，先按面值大小排序：:math:`c_1=1 \lt c_2 \lt c_3 \lt \cdots \lt c_n`。然后对 :math:`c_3` 到 :math:`c_{n-1}` 的各个面值依次进行反例检查。检查的金额就是恰好比下一个面值大的当前面值的倍数，即对于面值 :math:`c_i`\ ，我们计算出恰好比 :math:`c_{i+1}` 大的那个 :math:`c_i` 的倍数金额 :math:`a=pc_i`，用它来进行反例检查。对于这个金额，如果不采用贪心法就是要用 :math:`p` 张 :math:`c_i` 面值的钱，再计算一下用贪心法需要用几张钱，和 :math:`p` 进行比较看看贪心法是不是更优。只要找到一个反例，贪心法就被推翻了。如果找不到反例的话这套货币就适用贪心法，不需要再尝试找其他反例了（这个方法的证明很复杂，就不介绍了，记得方法就可以了）。

   请按上述方法对前面提高过的人民币、美元硬币、等比数列面值、奇怪的不适用贪心法的面值等进行验证。


至于可以使用贪心法的情况，程序的编写非常简单，以至于一般面向竞赛的OJ网站上都不会有完全使用贪心法即可解决的找零问题题目。比如力扣网站的322号和518号题目，都是找零问题，但是都不保证所有测试点都适用贪心法。但现在这个阶段请大家一定要自己动手编程试一试下面这个自编的问题：

.. admonition:: 人民币找零问题

   输入一个以元为单位的人民币金额 :math:`a\ge1`，使用1元、2元、5元、10元、20元、50元、100元七种人民币纸币来组合出这个金额。请使用贪心法计算出使用纸币数量最少的组合方法。

   输出格式：一行七个整数，分别表示1元、2元、5元、10元、20元、50元、100元七种纸币的使用数量，不使用的为0，数字之间用一个空格分隔。

.. admonition:: 附加练习

   输入任意一套 :math:`n` 种面值的货币，其中必须有一种面值为1。编程判断该套货币的找零问题能否适用贪心法。

整数最大拼接问题
^^^^^^^^^^^^^^^^^^^^^^^^

:strong:`整数拼接`\ 是指将数个非负整数按一定顺序首尾相接成为一个新的整数，一般来说要求每一个整数都出现在拼接成的新整数中，所以如果有0，不能拼接在最前面。例如0，12，345，可以拼接成123450，或者120345，或者345012，或者345120。:strong:`整数最大拼接问题`\ 就是给定 :math:`n` 个整数 :math:`\{a_1,a_2,\dots,a_n\}`\ ，找到它们能拼接出的最大整数，例如0，12，345能拼接出的最大整数是345120。

要找到能拼接出的最大整数，应该按照一定的策略从左到右的选择整数进行拼接。这个问题散发着浓浓的贪心法的气味，但是它的贪心策略却并不是那么直观的。

最容易想到的一个策略是从左到右尽量先选数值大的，例如前面举的例子就是按照345、12、0的顺序从大到小进行选择的。但事实如此吗？让我们看看这个例子：4个整数342、45、7、98，如果按照最大者优先的策略，拼接得到的整数为34298457，而正确答案为98745342。

所以第二种容易想到的策略是把整数最高位对齐之后从高位向低位逐位比较大小，也就是类似字符串的“字典序”比较，优先取字典序大者。例如上面这个例子的四个数如果视作字符串按字典序排序，那么排序结果为 ``"342"<"45"<"7"<"98"``\ ， 依字典序大者优先的策略拼接就能得到正确结果98745342。然而这就是正确的策略了吗？既然这么问，那么答案肯定是No了。请看这两个整数：12、121。按照字典序的规则，12小于121，所以拼接结果为12112，但正确答案却是12在前、121在后的12121。

事实上，无论用数值比较还是用字典序比较，都只有在两个数的位数完全相同的情况下才能确保正确。为了寻找一个正确的贪心策略，我们必须为这个问题设计一种新的顺序，那就是直接比较拼接之后的数值大小来确定先后顺序。

首先来看两个非负整数的情况，:math:`a` 和 :math:`b`\ ，各有 :math:`A` 位和 :math:`B` 位，一共有两种拼接：:math:`\overline{ab}=a\times10^{B}+b` 和 :math:`\overline{ba}=b\times10^A+a`\ 。我们直接比较两个拼接后得到的新整数，如果 :math:`\overline{ab}\gt\overline{ba}`\ ，那么在拼接时就应该 :math:`a` 先于 :math:`b`\ ，记作 :math:`a\prec b`\ ；反之，若 :math:`\overline{ab}\lt\overline{ba}`\ ，那么在拼接时就应该 :math:`b` 先于 :math:`a`\ ，记作 :math:`b\prec a`\ ；若拼接后的两个新整数相等，那么谁先谁后都没有关系，二者先后序相等，用等于号表示。和数值的小于等于关系类似，我们也可以有先于或等于关系 :math:`\preceq`\ 。

.. hint::

   请回忆一下我们在基础算法的排序章节中介绍过的相关知识点。

现在拓展到两个以上非负整数拼接的情况。对于给定的 :math:`n` 个整数，如果能够得到先后序关系 :math:`a_{i_1} \preceq a_{i_2} \preceq \cdots \preceq a_{i_n}` 并按这个顺序拼接，那么就能得到最大整数 :math:`\overline{a_{i_1}a_{i_2}\cdots a_{i_n}}`\ 。也就是说，我们在进行拼接时优先选择先后序\ :strong:`最先`\ 的数。为了证明这个贪心策略的正确性，可以使用微扰法，但是我们首先要证明先后序具有可传递性。即要证明：如果 :math:`a \prec b` 而且 :math:`b\prec c`\ ，那么 :math:`a\prec c`\ 。要证明这个性质并不难，大家可以自己动手试一试。

现在假设按照最先者拼接在最左的贪心策略得到了上述拼接结果 :math:`\overline{a_{i_1}a_{i_2}\cdots a_{i_n}}`\ ，满足 :math:`a_{i_1} \preceq a_{i_2} \preceq \cdots \preceq a_{i_n}`\ 。如果对这个拼接序列引入微扰，交换其中任意两个数。根据先后序的传递性，这样的扰动必然带入了至少一个可能的逆序对 :math:`\cdots\overline{a_ja_k}\cdots,a_k\preceq a_j`\ 。那么在这个片段上，扰动带来的新数值 :math:`\overline{a_ja_k}\le\overline{a_ka_j}`\ ，整体的拼接结果也一定只会变小不会变大。如果这不是扰动带来的唯一一个可能逆序对，那么其他的片段处也都一样有可能局部变小了，从而整个拼接的结果当然也只可能是变小了，最多不变，总归不可能会增大。这就证明了我们的贪心算法的正确性。

最后我们来看看怎样编写实际的程序。程序首先输入一个整数 :math:`n\gt 1`\ ，然后连续输入 :math:`n` 个整数 :math:`0\le a_i\le 10^9,i=1,\dots,n`\ ，要求输出最大的拼接整数。

**1、定义数据类型**

根据前面的算法描述，我们要对输入的数依拼接先后序进行排序。

我们可以给排序函数传入一个自定义的比较函数，它进行先于比较：:math:`\overline{ab}=a\times10^{B}+b \gt \overline{ba}=b\times10^A+a`\ ，这个很简单：

.. code-block:: c++

   bool cmp(int a, int b) {
           long long la = 10, lb = 10;     // 10^A 和 10^B
           while (a / la) la *= 10;        // 计算 10^A
           while (b / lb) lb *= 10;        // 计算 10^A
           return a * lb + b > b * la + a;
   }

但是仔细一想，这种方法虽然可行但是效率堪忧。因为在对整个数组进行排序的时候，要不断地进行两两比较，每一个数都会被多次作为参数调用这个比较函数，里面的两个循环会被重复执行很多次。这是一种极大的浪费，因为对于每一个数 :math:`a_i`\ ，:math:`10^{A_i}` 都只需要计算一次就够了。所以我们何不定义一个结构来存放每一个数本身以及它的10的位数次方呢？我们可以重载输入流运算以便在读数的同时就计算好所有数的10的位数次方。并且可以重载这个结构类型的小于运算，实现先于运算，这样就不需要提供自定义比较函数了。

于是就有了下面的代码：

.. literalinclude:: ../../codes/413_lc179.cpp
   :language: c++
   :lines: 7-23

算法的主程序于是变得极为简单，建立一个 ``vector<Element>`` 向量，逐个读入整数，然后用 ``sort()`` 函数完成排序。这里可以使用不稳定排序，因为两个相等的数谁先谁后没有关系。最后把排完序的数逐个按先后次序输出即可。

需要注意最后输出时有一个隐蔽的陷阱：如果输入的整数全为0的话，就不能逐个输出所有数，只需要输出一个0就可以了。这个陷阱要用特判来处理，共有两种特判方法：

1. 事前特判。在输入数据的同时我们就判断是否输入的全为0。但要千万小心，虽然输入的数据没有负数，但仍然不能用全部求和的方法判断是不是全部为负数，因为数据的取值范围很大，所有数据的总和有可能会整数溢出。

2. 事后特判。在排完序之后，检查第一个（最先一个）数是不是0，如果是0那么说明全零，这时候输出最先一个数之后，后面的数就不用再输出了。这是因为根据我们定义的先后序规则，0比任何正数都要更后，所以除非输入的数全为0，否则0不会出现在最先的位置上。

综合比较起来，还是事后特判的方法更好一些，请看完整的源程序：

.. literalinclude:: ../../codes/413_lc179.cpp
   :language: c++

力扣网站的179号题就是一个类似的题目，用我们这个算法可以测试通过，并且速度非常之快。