ABC備忘録[ABC160 C - Traveling Salesman around Lake] (Python)

問題文

1周$K$メートルの円形の湖があり、その周りに$N$軒の家があります。
$i$番目の家は、湖の北端から時計回りに$A_i$メートルの位置にあります。
家の間の移動は、湖の周りに沿ってのみ行えます。
いずれかの家から出発してN軒すべての家を訪ねるための最短移動距離を求めてください。

制約

$2≤K≤10^6$
$2≤N≤2×10^5$
$0≤A_1<...<A_N<K$
入力中のすべての値は整数である。

C - Traveling Salesman around Lake

解法

家は円周上に並んでいると考えることができるので、隣り合う家同士の距離をそれぞれ求め、それらのうちもっとも大きいものを除外したものの和を取ればよい。

K, N = map(int,input().split())　
A = list(map(int, input().split()))

li = []
for i in range(N - 1):
  li.append(A[i + 1] - A[i]) #liに対して配列Aの要素間の差分を追加

li.append(abs(A[0] + (K - A[-1]))) #配列の初項と末項のみ別で追加
print(sum(li) - max(li))