Why will this approach produces always the correct output?

Revision en1, by v-O_O-v, 2019-09-16 15:32:48

I have solved 285C - Получаем перестановку using a greedy approach i.e sort all the values and then count the number of moves to make first element 1, the next to 2 and so on... But how can we come to the conclusion that this is always optimal and produces the minimum number of moves?

Tags #proof

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English v-O_O-v 2019-09-16 15:32:48 329 Initial revision (published)