Reminder: in case of any technical issues, you can use lightweight websites m1.codeforces.com, m2.codeforces.com or m3.codeforces.com ×

EonHino's blog

By EonHino, history, 5 months ago, In English,

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) = 6

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

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by EonHino (previous revision, new revision, compare).