CFR 622 D. Optimal Number Permutation ( Ad hoc )
題意:
要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列,使得以下 s 最小。
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 )