2010-1101

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

本题可以直接通过贪心解决，比较类似于Huffman编码。贪心策略的正确性，我们可以将整个游戏过程，用一个多项式表示。将此多项式展开即可证明一下两种策略分别为游戏结果最大和最小的最优策略。
如果要使最终游戏的结果最大，我们采取的策略是：不断从当前的数集中取出两个最小的数，按题目中所给出的方式进行运算后，我们将这两个数字从原数集中删除，并将这个新得到的数加入数集之中；不断进行此操作，直到数集中只有一个数为止。此时，数集中的这个数字就是结果最大的数值。类似的，要使游戏的结果最小，我们可以每次从数集中取出K个最大的数，进行运算后重新放入数集，直到数集中的数字唯一。有一点要注意的是，最后一次运算时，数集中的数字个数可能会小于K个，这时只要把剩下的所有这些数字进行运算即可。另外，由于这个题涉及较多乘法运算，在实现上需要采用高精度。
不断取最值的方法，我们可以用两个有序队列来实现：一个队列存放已排序的初始数字，另外一个队列存放运算之后得到的中间结果。很显然，通过上述策略得到的中间结果序列是单调的。这样，我们就可以不断从这两个队列中取得数值进行运算，直到这两个队列为空。最终的运算结果即为游戏的结果。
[by zykpeter]

本题可以直接通过贪心解决，比较类似于Huffman编码。贪心策略的正确性，我们可以将整个游戏过程，用一个多项式表示。将此多项式展开即可证明一下两种策略分别为游戏结果最大和最小的最优策略。

如果要使最终游戏的结果最大，我们采取的策略是：不断从当前的数集中取出两个最小的数，按题目中所给出的方式进行运算后，我们将这两个数字从原数集中删除，并将这个新得到的数加入数集之中；不断进行此操作，直到数集中只有一个数为止。此时，数集中的这个数字就是结果最大的数值。类似的，要使游戏的结果最小，我们可以每次从数集中取出K个最大的数，进行运算后重新放入数集，直到数集中的数字唯一。有一点要注意的是，最后一次运算时，数集中的数字个数可能会小于K个，这时只要把剩下的所有这些数字进行运算即可。另外，由于这个题涉及较多乘法运算，在实现上需要采用高精度。

不断取最值的方法，我们可以用两个有序队列来实现：一个队列存放已排序的初始数字，另外一个队列存放运算之后得到的中间结果。很显然，通过上述策略得到的中间结果序列是单调的。这样，我们就可以不断从这两个队列中取得数值进行运算，直到这两个队列为空。最终的运算结果即为游戏的结果。

[by zykpeter]