최종 울트라-퀵 소트 > 문제은행



문제은행

1148 : 최종 울트라-퀵 소트

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 40 회    시도횟수: 113 회   



범수는 새로운 정렬 알고리즘을 만들어내고, 여기에 '울트라-퀵 소트'라는 이름을 붙였다. 이 알고리즘은 인접한 두 수를 서로 바꿔서 주어진 수열을 오름차순으로 정렬한다

수열이 주어지면 그것을 정렬하기 위해 수들을 최소 몇 번 교환해야 하는지 계산해서, '울트라-퀵 소트'가 별로 쓸 일이 없다는 것을 범수에게 알려주자.




첫 줄에 수열의 크기 n(n<=500,000)이 입력된다. 이후 n개의 줄에 수열의 각 원소(0≤a[i]<10억)가 차례대로 주어진다.

단, 데이터의 70%는 n이 10,000보다 작다.




첫 줄에 필요한 교환 연산의 수를 출력한다.



5
13
3
2
9
6
6






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.