ABC memorandum [ABC160 C --Traveling Salesman around Lake] (Python)

Problem statement

There is a circular lake of $ K $ m per lap, around which there are $ N $ houses. The $ i $ th house is located $ A_i $ meters clockwise from the northern end of the lake. You can only move between houses along the circumference of the lake. Find the shortest travel distance to start from one of the homes and visit all N homes.

Constraint

2≤K≤10^6 2≤N≤2×10^5 0≤A_1<... All values being entered are integers.

C - Traveling Salesman around Lake

solution

Houses can be thought of as being lined up on the circumference, so the distance between adjacent houses should be calculated and the sum of those excluding the smallest one should be taken.

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]) #Add the difference between the elements of array A to li
  
li.append(abs(A[0] + (K - A[-1]))) #Only the first and last terms of the array are added separately
print(sum(li) - max(li))

Recommended Posts

ABC memorandum [ABC160 C --Traveling Salesman around Lake] (Python)
ABC memorandum [ABC163 C --managementr] (Python)
ABC memorandum [ABC159 C --Maximum Volume] (Python)
ABC memorandum [ABC161 C --Replacing Integer] (Python)
ABC memorandum [ABC158 C --Tax Increase] (Python)
ABC memorandum [ABC157 C --Guess The Number] (Python)
ABC147 C --HonestOrUnkind2 [Python]
ABC163 C problem with python3
ABC188 C problem with python3
ABC187 C problem with python
Solve ABC163 A ~ C with Python
ABC127 A, B, C Explanation (python)
ABC166 in Python A ~ C problem
Solve ABC168 A ~ C with Python
Solve ABC036 A ~ C in Python
Solved AtCoder ABC 114 C-755 with Python3
Solve ABC162 A ~ C with Python
Solve ABC167 A ~ C with Python
ABC128 A, B, C commentary (python)
Solve ABC158 A ~ C with Python
ABC126 A, B, C Explanation (python)
Solve ABC037 A ~ C in Python
Solve ABC175 A, B, C in Python
Python Memorandum 2
Algorithm in Python (ABC 146 C Binary Search
Python memorandum
python memorandum
python memorandum
Python: I tried the traveling salesman problem
Python memorandum
python memorandum
Python memorandum
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Beginner ABC156 (Python)
Python basics memorandum
Python pathlib memorandum
Python memorandum (algorithm)
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
Beginner ABC155 (Python)
python C ++ notes
python, openFrameworks (c ++)
Beginner ABC157 (Python)
Python memorandum [links]
AtCoder ABC 175 Python
Solve Atcoder ABC176 (A, B, C, E) in Python