请教用贪心算法求解数列的极差M问题在黑板上写了N个正整数作成的一个数列,进行如下操作：每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在

Question

请教用贪心算法求解数列的极差M问题
在黑板上写了N个正整数作成的一个数列,进行如下操作：每一次擦去其中的两个数a和b,然后在数列中加入一个数a×b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的max,最小的为min,则该数列的极差定义为M=max-min.希望大家能给出具体实现的算法(C/C++)
可以参照下面的提示来写：
把求解max与min的过程分开，着重探讨求max的问题。
讨论：假设经（N－3）次变换后得到3个数：a,b,max'（max’≥a≥b），其中max’是（N－2）个数经（N－3）次f变换后所得的最大值，此时有两种求值方式，设其所求值分别为 则有：＝（a×b＋1）×max’＋1，＝（a×max’＋1）×b+1 所以 － ＝max’－b≥0若经（N－2）次变换后所得的3个数为：b（m≥a≥b）且m不为（N－2）次变换后的最大值，即m＜max’则此时所求得的最大值为：＝（a×b+1）×m+1 此时 － ＝（1+ab）（max’－m）＞0 所以此时不为最优解。
所以若使第k（1≤k≤N－1）次变换后所得值最大，必使（k－1）次变换后所得值最大（符合贪心策略的特点2），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数p，q施加f操作：p←p×q+1，q←∞即可，因此此题可用贪心策略求解。讨论完毕。
在求min时，我们只需在每次变换的数列中找到两个最大数p，q施加作用f：p←p×q+1，q←-∞即可．原理同上。

Answer 1

假设经（N－3）次变换后得到3个数：a,b,max'（max’≥a≥b）,其中max’是（N－2）个数经（N－3）次f变换后所得的最大值,此时有两种求值方式,设其所求值分别为 ,,则有：＝（a×b＋1）×max’＋1,＝（a×max’＋1）×b+1 所以 － ＝max’－b≥0若经（N－2）次变换后所得的3个数为：m,a,b（m≥a≥b）且m不为（N－2）次变换后的最大值,即m＜max’则此时所求得的最大值为：＝（a×b+1）×m+1 此时 － ＝（1+ab）（max’－m）＞0 所以此时不为最优解.
所以若使第k（1≤k≤N－1）次变换后所得值最大,必使（k－1）次变换后所得值最大（符合贪心策略的特点2）,在进行第k次变换时,只需取在进行（k－1）次变换后所得数列中的两最小数p,q施加f操作：p←p×q+1,q←∞即可,因此此题可用贪心策略求解.讨论完毕.
在求min时,我们只需在每次变换的数列中找到两个最大数p,q施加作用f：p←p×q+1,q←-∞即可．原理同上