CS Academy Round #39: B. Circle Elimination

,

https://csacademy.com/contest/round-39/task/circle-elimination/

これは問題文が楽。

solution

配列$a$は添字 $\mapsto$ 値の関数として見れるが(値, 添字)の対の列として見て整列すれば、順に舐めて隣接項間の距離の総和が答え。$O(N \log N)$。

implementation

#!/usr/bin/env python3
import random
n = int(input())
a = list(map(int, input().split()))
b = [ None ] * n
for i, a_i in enumerate(a):
    b[i] = ( a_i, i )
b.sort()
result = 0
for i in range(n - 1):
    k = abs(b[i + 1][1] - b[i][1])
    result += min(k, n - k)
print(result)