本关任务:将 n 个正整数作成的一个数列,进行如下操作:每一次删除其中的两个数 a 和 b,然后在数列中加入一个数a×b+1,如此下去直至数列中剩下一个数。 在所有按这种操作方式最后得到的数中,最大的记作 max,最小的记作 min,则该数列的极差定义为m=max-min,请你使用贪心算法设计编程输出他们的极差。
时间: 2023-04-27 11:06:29 浏览: 297
首先,我们需要明确一个事实:无论删除哪两个数,加入的新数都是一样的,即 a×b+1。因此,我们可以考虑每次删除两个数中较小的那个数和当前最小值 min 相乘再加 1,得到新的最小值,同理,每次删除两个数中较大的那个数和当前最大值 max 相乘再加 1,得到新的最大值。这样,我们就可以在每次操作后更新最小值和最大值,直到数列中只剩下一个数。
具体实现时,我们可以使用一个优先队列(堆)来存储数列中的所有数,每次从队列中取出两个最小的数进行操作,将得到的新数加入队列中,直到队列中只剩下一个数。最后,计算得到的最大值和最小值的差即为该数列的极差。
因此,本题的贪心策略为:每次取出两个最小的数进行操作,得到新数后加入队列中,直到队列中只剩下一个数。
阅读全文