Maximizing the value of a permutation with the least swap operators.
Difference between en3 and en4, changed 2 character(s)
### 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 $\sum\limits_{i=2}^{n}{|p_{i} - p_{i - 1}|}$↵
↵
↵
### 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 &mdash; 3) + abs(4 &mdash; 1) + abs(2 &mdash; 4) = 46↵
↵
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)