fork(1) download 
  1. import sys
  2.  
  3. def solve():
  4.     n = int(sys.stdin.readline())
  5.     a = list(map(int, sys.stdin.readline().split()))
  6.  
  7.     if n % 2 == 1:
  8.         # Partition into one block of size 3 and (n-3)/2 blocks of size 2.
  9.         # We iterate through all n possible starting positions for the size-3 block.
  10.  
  11.         c2 = [(abs(a[i] - a[(i + 1) % n])) for i in range(n)]
  12.  
  13.         s_even = 0
  14.         s_odd = 0
  15.         for i in range(n):
  16.             if i % 2 == 0:
  17.                 s_even += c2[i]
  18.             else:
  19.                 s_odd += c2[i]
  20.  
  21.         min_cost = float('inf')
  22.  
  23.         for i in range(n):
  24.             # Block of size 3 starts at index i
  25.             # The elements are a[i], a[i+1], a[i+2]
  26.  
  27.             # Cost for the block of 3
  28.             v1 = a[i]
  29.             v2 = a[(i + 1) % n]
  30.             v3 = a[(i + 2) % n]
  31.  
  32.             elements = sorted([v1, v2, v3])
  33.             median = elements[1]
  34.             cost3 = abs(v1 - median) + abs(v2 - median) + abs(v3 - median)
  35.  
  36.             # Cost for the remaining n-3 elements, paired up
  37.             # These are pairs (i+3, i+4), (i+5, i+6), ...
  38.             # The c2 costs are c2[i+3], c2[i+5], ...
  39.  
  40.             cost_pairs = 0
  41.             if i % 2 == 0:
  42.                 cost_pairs = s_odd - c2[(i + 1) % n]
  43.             else:
  44.                 cost_pairs = s_even - c2[(i + 2) % n] - c2[i]
  45.  
  46.             total_cost = cost3 + cost_pairs
  47.             min_cost = min(min_cost, total_cost)
  48.  
  49.         print(min_cost)
  50.  
  51.     else:
  52.         # Partition into n/2 blocks of size 2.
  53.         # Two possible pairing strategies.
  54.  
  55.         # Strategy 1: pairs (0,1), (2,3), ...
  56.         cost1 = 0
  57.         for i in range(0, n, 2):
  58.             cost1 += abs(a[i] - a[i + 1])
  59.  
  60.         # Strategy 2: pairs (1,2), (3,4), ..., (n-1,0)
  61.         cost2 = 0
  62.         for i in range(1, n, 2):
  63.             cost2 += abs(a[i] - a[(i + 1) % n])
  64.  
  65.         print(min(cost1, cost2))
  66.  
  67.  
  68. def main():
  69.     t = int(sys.stdin.readline())
  70.     for _ in range(t):
  71.         solve()
  72.  
  73. if __name__ == "__main__":
  74.     main()
Success #stdin #stdout 0.13s 14160KB
comments (?)
stdin 
4
5
1 1 1 1 1
4
2 100 99 3
5
2 2 5 9 5
6
1 1 1 2 1 2
stdout 
0
2
7
2
https://ideone.com/Uz6Lrw
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!