Énoncé du problème
Il y a un lac circulaire de $ K $ m par tour, autour duquel il y a des maisons $ N $. La $ i $ ème maison est située $ A_i $ mètres dans le sens des aiguilles d'une montre à partir de l'extrémité nord du lac. Vous ne pouvez vous déplacer qu'entre les maisons le long de la circonférence du lac. Trouvez la distance parcourue la plus courte pour visiter toutes les N maisons à partir de l'une des maisons.
C - Traveling Salesman around Lake
Puisque les maisons peuvent être considérées comme alignées sur la circonférence, la distance entre les maisons adjacentes doit être calculée et la somme de celles excluant la plus petite doit être prise.
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]) #Ajouter la différence entre les éléments du tableau A à li
li.append(abs(A[0] + (K - A[-1]))) #Ajouter uniquement les premier et dernier termes de la séquence séparément
print(sum(li) - max(li))
Recommended Posts