KOI 2차 2020 중3- 버블버블 > 문제은행 : 정보올림피아드&알고리즘




4604 : 버블버블

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

문제

여러분은 N개의 정수 A1, ··· , AN을 버블 정렬(bubble sort)를 이용하여 단조증가하도록 (감소하지 않는 순서가 되도록) 정렬하려고 한다. 주어진 정수들 중에는 같은 값이 있을 수 있다. 버블 정렬은 인접한 두 수를 교환하는 것 만으로 정렬을 수행한다. 버블 정렬을 수행하는 동안 인접한 두 수를 몇 번 교환해야 하는지도 셀 수 있다. 예를 들어, 세 수 3, 2, 1이 주어졌다면, 첫 단계에서는 인접한 두 수를 교환하는 일을 두 번 해서 2, 1, 3을 만들고, 다음 단계에서는 2와 1을 교환해서 1, 2, 3을 만든다. 총 3번의 교환이 필요하다.

 

이제 이를 약간 변형한 문제를 풀어보자. 주어진 N개의 수 중 정확하게 한 개의 수를 다른 임의의 수로 바꿀 수 있다. 처음 주어진 수들은 모두 정수였지만, 바뀐 수는 실수의 어떤 값으로든 될 수 있다. 이렇게 하나의 수를 바꾼 다음, N개의 수를 단조증가하도록 버블 정렬을 수행할 때 교환 횟수가 최소가 되게 하려고 한다.

 

물론, 어떤 수를 바꾸느냐에 따라 필요한 최소 교환 횟수는 달라질 수 있다. 예를 들어, 위의 예 3, 2, 1에서 맨 마지막 수를 4로 바꾸면 (실제로는 3 이상인 어떤 수도 가능하다) 단 한 번 3과 2를 바꾸어서 오름차순으로 정렬된 2, 3, 4를 얻을 수 있다. 한편, 두 번째 수인 2를 바꾸는 경우 어떤 수로 바꾸더라도 최소한 두 번 교환을 해야 한다는 것을 알 수 있다.

 

1 이상 N 이하의 모든 i에 대해, Ai를 바꾸었을 때 버블 정렬의 최소 교환 횟수를 모두 구하는 프로그램을 작성하라.


 


제약 조건

  • 1 ≤ N ≤ 300 000
  • 1 ≤ A1, · · · , AN ≤ 1 000 000

부분문제

  1. (6점) N ≤ 200, A1, · · · , AN ≤ 200.
  2. (13점) N ≤ 3,000, A1, · · · , AN ≤ 3,000.
  3. (21점) N ≤ 15,000, A1, · · · , AN ≤ 15,000.
  4. (60점) 추가 제약 조건 없음.​

입력형식

첫 번째 줄에 N이 주어진다. 두 번째 줄에 N개의 정렬할 수 A1, A2, ··· , AN이 공백 하나를 사이로 두고 주어진다. 이 수들은 모두 정수이다. 


출력형식

첫 번째 줄에 문제의 정답을 출력한다. 

i번째로 출력해야 할 수는, Ai를 아무 실수로 바꿀 수 있을 때 N개의 수를 단조증가하도록 버블 정렬하기 위해 필요한 최소 교환 횟수이다. 


입력 예

3
3 2 1

출력 예

1 2 1

입력 예

5
6 6 8 5 8

출력 예

2 3 3 0 3


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP