inversion1 cf #653 div3 F - Cyclic Shifts Sorting (그리디, constructive, sorting, inversion) https://codeforces.com/contest/1374/problem/F 소팅 문제에서 inversion개수로 규칙찾기 원소의 수가 n개인 배열 a에서 다음 연산을 최대 $n^2$번 수행하여 정렬하여라. 정렬 못하면 -1 출력 1. i번째 원소를 맨 앞으로 가져올 수 있다. 2. a의 원소가 모두 distinct하면 위 operation으로 inversion 개수의 parity를 바꿀 수 없다. 따라서 이 때 inversion 개수의 parity가 홀수면 정렬 불가능하다. 3. a의 원소에 중복 원소가 있다면 일단 distinct한 배열로 바꿔준 후에, inversion 개수의 parity가 홀수라면 중복 원소 한 쌍을 swap하여 parity를 짝수로 맞춰주면 된다. 예를들어 $a = [2,1.. 2020. 7. 13. 이전 1 다음
