在一个遥远的王国里,有一座高耸入云的宝塔,据说里面藏有神秘的宝藏。但是,进入宝塔的道路异常困难,需要经过各种险阻,其中一个重要的关卡是“平衡之门”。
平衡之门是一条走廊,两边是无数个数码显示屏幕,每个屏幕上都显示着一个整数。在走廊中央有一个控制台,上面有两个按钮,一个是“乘2”按钮,一个是“除以2”按钮。每次按下其中一个按钮,控制台上的数字就会相应地变化。走廊中的每个数字最多只能被操作一次。
王国的宝藏猎人们想要通过平衡之门,以最小的代价进入宝塔。他们发现,只需要选择恰好 k 个数字,使得每个数字经过不超过一次的操作后,可以得到所有的数字,就可以顺利通过平衡之门。现在他们需要你的帮助,计算出最小的极差,即经过操作后最大值和最小值之差的最小值。
第一行输入两个正整数 n 和 k ,代表数组长度以及选择的元素数量。
第二行输入n个元素,代表给定的数组。
1≤k≤n≤105
1≤ai≤109
k 次操作后,数组极差的最小值。
输入输出示例仅供调试,后台判题数据一般不包含示例
输入
4 2
1 4 3 5
输出
2
输入
6 1
9 4 3 4 2 5
输出
3
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.