题目内容

在一个遥远的王国里，有一座高耸入云的宝塔，据说里面藏有神秘的宝藏。但是，进入宝塔的道路异常困难，需要经过各种险阻，其中一个重要的关卡是“平衡之门”。

平衡之门是一条走廊，两边是无数个数码显示屏幕，每个屏幕上都显示着一个整数。在走廊中央有一个控制台，上面有两个按钮，一个是“乘2”按钮，一个是“除以2”按钮。每次按下其中一个按钮，控制台上的数字就会相应地变化。走廊中的每个数字最多只能被操作一次。

思路

1.观察到每个数最多修改一次，那么显然最优的修改方案一定是前$i$小都乘以2，前$k-i$大都除以2。

2.那么排序,枚举$i$然后模拟这个过程，去求最大值最小值，复杂度达到$O(n^2)$ 。但好在我们只关心极差，即最大值和最小值，所以不需要去模拟操作每一个数。而是考虑一次操作后结果会分成三段,分别去求这三段的最值就好了。如下图所示,我们只需要从这六个红圈中取极值即可。

代码