数列极差

问题补充说明：求数列极差算法！！！ 只要算法就可以了！

以下是极差问题可用贪达东婪算法的一点资料，请斟酌：

数列极差问题

在黑板上写了N个正整数组成的一个数列，进行如下操作：每次擦去其中的两个跳回孙架挥承奏许明硫数a和b，然后在数列中加入一个数a×b＋1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min，则该数列的极差定义为M＝max－min。

贪心算法：每次擦出数列来自中的两个最小数，产生最大值max；

每次擦出数列中的两个最大数，产生最小值min；

下面我们以360问答求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个数为：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←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。镇吧血看生讨论完毕。

在求min时，我们只需在每次变换的数列中找到两个最大数p，q施加作用f：p←p×q+1，q←-∞即可．原理同上。

我有贪婪算法的ppt,你如果要的话,留下邮箱,我会发给你的.

标签：极差,数列