otteru   1년 전

저는 merge_sort로 부분정복해서 풀었는데 밑의 코드에서 index2-k를 result에 더해서 swap 수를 찾는 방식이었는데
밑의 코드를 그대로 사용하면 5n%에서 틀립니다.

반례

3
5 1 5

답: 1
오류: 2

이게 temp[index1] <= temp[index2]로 가져가서 같은 경우에 index2가 그 경우를 가져가버리면 같은 것도 swap한걸로 result에 값이 추가되서 
temp[index1] = temp[index2]인 경우에는 index1이 가져가서 처리하도록 해야 합니다.

댓글을 작성하려면 로그인해야 합니다.