題意
- 整数n個が与えられる
- 連続しなくても良い適当な要素をy個選ぶ．
- この選んだどの要素の差も、この選んだ要素の最大値以上でないといけない
例
- NG: [0,1,2]を選んだとき、最小の差は1であり、最大値の2未満であるため選べない
- OK: [0,0,0]を選んだとき、最小の差は 0 であり、最大値0以上であるためよい
- OK: [-1, 3]を選んだとき、最小の差は 4 であり、最大値3以上である
- OK: [ 0, 3]を選んだとき、最小の差は3であり、最大値3以上である
こう考えた:
まず、適当な数列a を選び、 これをソートしたとき、$a_0, a_1, ... , a_(n-1)$とすると、隣接する２項間の最小値がすべて$a_(n-1)$以上であるかが焦点になる．これは、最小の差がある値以上であるかの判定を行いたいので、隣接する差の最小値に注目すべきであるからだ．
ところで、2つの値$x、y$があったときに$x, y (x ¥leq y)$が厳密な正の値であるとき、条件を満たせない．なぜなら、$(y - x) < y$であるためである．(2値の差はy以下になってしまう)
次に、2つの値$x,y$が、$ x、y leq 0 $だったとき、必ず条件を満たせる．なぜなら、2値の差は必ず0以上であるため、最大値が$x, y$ 未満であることはない．
これらを合わせると、以下のことが言える．
- この配列には、厳密に正の整数は1つ以上入らない．
- この配列には、0以下の整数はいくつ入れても良い.
このため、以下の処理を行う．
- 0以下の整数全てをとり、ソートして、隣合う差の最小値を$m$とする
- 整数のうち最小の値があればそれを１つだけ取り、処理を打ち切り答えとする
- 他に取れる数があったとしても、それは条件に引っかかるので取れない