Maximizing the value of a permutation with the least swap operators.

Revision en3, by EonHino, 2018-11-16 07:42:48

Statement

Given n (n is even number and n <= 168) and a permutation of n. Our task is to do the least swap operator so that the value of

the permutation is maximum.

The value of a permutation is

Input

4

1 2 3 4

Output

3

Explain

1 2 3 4

Swap (p[1], p[3]) : 3 2 1 4

Swap (p[3], p[4]) : 3 2 4 1

Swap (p[2], p[4]) : 3 1 4 2

The value of the permutation now is abs(1 — 3) + abs(4 — 1) + abs(2 — 4) = 4

And we do 3 swap operators so the output is 3.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English EonHino 2018-11-16 17:01:35 2 Tiny change: 'ash; 4) = 4\n\nAnd we' -> 'ash; 4) = 6\n\nAnd we'
en3 English EonHino 2018-11-16 07:42:48 4 Tiny change: 'limits_{i=1}^{n-1}{|p_{i} -' -> 'limits_{i=2}^{n}{|p_{i} -'
en2 English EonHino 2018-11-16 07:39:22 0 (published)
en1 English EonHino 2018-11-16 07:37:10 645 Initial revision (saved to drafts)