abc-361 Cを解いてみました

問題

長さ$N$の数列から$K$要素を自由に選んで消し，残った要素を順序を保って連結
その数列における（最大値）-（最小値）としてありうる最小値を求めよ．

考え方

（最大値）-（最小値）をもとの数列より小さくしたい場合，もとの数列の最大値か最小値は取り除く必要がある

• 具体例（数列がソートされてる場合）
  • [1, 2, 3, 5, 7] から1つ取り除く場合
    • 1 あるいは 7 を取り除く必要がある
  • [1, 2, 3, 5, 7] から2つ取り除く場合
    • 左から2つ [1,2] を取る，左と右から1つずつ 1, 7 を取る，右から [5, 7] を取る，のいずれかを行う

$k$個取り除く場合，右から$x$個，左から$(k-x)$個取り除くとよい

ソートの計算量は$n \log n$，$n < 2 \times 10^5$より，時間内に計算可能
右から取り除く数$x$については，全探索の計算量が$k$のため大丈夫

実装したコード

n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

mini = max(a)

for x in range(k+1):

  if mini > a[-(k-x)-1] - a[x]:
    mini = a[-(k-x)-1] - a[x]

print(mini)