Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 622 D. Optimal Number Permutation ( Ad hoc )

Problem - 622D - Codeforces

題意:
要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列,使得以下 s 最小。
f:id:h0rnet:20170505194932p:plain
d[ i ] 為 i 處於的兩個位置形成的距離。

制約:
1 ≤ N ≤ 5e5

解法:
看解說,覺得非常神祕,遇到類似題應該還是不會。
主要想法是這樣,猜測可以直接構造出 s = 0 的排列。
如果可以令 d[ i ] 總是等於 n - i 就會很優。
可以發現如果這樣分配: ( 1, n - 1 ), ( 2, n - 2 ), ( 3, n - 3 )
距離變化是 n - 2, n - 4, n - 6, ...
所以考慮奇數和偶數分開處理,就能這樣頭尾夾擊構造。

時間 / 空間複雜度:
O( N )

N = int( input() )
ans = [ N for i in range( 2 * N ) ]
for i in range( 1, N + 1 ):
  x = i // 2 if i & 1 else N - 1 + i // 2
  y = x + N - i
  ans[ x ], ans[ y ] = i, i
print( *ans )