数列极差问题

数列极差问题

测试数据来自 wjszez/2011

问题描述:在黑板上写了N个正整数作成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a*b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的max,最小的为min,则该数列的极差定义为M=max-min。

分析: 思路分析:例如数列1,2,3.按照极差的定义,我们算算这个数列的极差。他有三种情况:(1*2+1)3+1=10,(23+1)1+1=8,(13+1)*2+1=9.我们发现当先算两个较小的数是,得到的是最大值,当先算两个较大的数时,得到的是最小值。因此,我们按照这个思路来解决这个问题。这个问题是求最小值和最大值,然后它们相减,因此我们需要将输入数组逆序的拷贝。至于为啥是逆序的,代码中解释。当我们求出最大和最小的两个数之后,我们记录他们的位置。但是,之后,这两个数将不能用了,因此我们用算出的那个值覆盖他们。

信息

ID
2420
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者