실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
길이가 ()인 부울 배열 에서 민철과 수민이 게임을 하고 있습니다. 민철의 점수는 의 첫 절반에서의 역전 수였고, 수민의 점수는 의 두 번째 절반에서의 역전 수였습니다. 역전이란 와 인 한 쌍의 항목으로, 입니다. 예를 들어, 0의 블록 다음에 1의 블록이 있는 배열에는 역전이 없으며, 의 1이 뒤따르는 의 0의 블록이 있는 배열은 의 역전을 가지게 됩니다.
지나가는 선생님이 우연히 게임하는 두 사람을 발견했고, 게임이 동점인 것처럼 보이게 하기 위해 필요한 인접한 요소 사이에 최소 교환 횟수를 알고 싶어합니다.
입력의 첫 번째 줄에는 이 주어지고, 다음 줄에는 0 또는 1인 개의 정수가 주어집니다.
게임이 비길 수 있는 인접한 교환 횟수를 적어주세요.
5 0 0 0 1 0 1 0 0 0 1
1
이 예에서, 배열의 첫 절반은 처음에 1번의 역전을 가지고 있고, 두 번째 절반은 3번의 역전을 가지고 있습니다. 번째와 번째 비트를 서로 교환하면 두 하위 배열 모두 역전이 개가 됩니다.
출처: USACO 2019 US Open Contest, Gold Problem 3. Balancing Inversions