파일 업로드

🎨AI 리소스 생성

프롬프트 없음

균형 잡힌 역전

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

길이가 2N2N (1N1051 \leq N \leq 10^5)인 부울 배열 AA에서 민철과 수민이 게임을 하고 있습니다. 민철의 점수는 AA의 첫 절반에서의 역전 수였고, 수민의 점수는 AA의 두 번째 절반에서의 역전 수였습니다. 역전이란 A[i]=1A[i]=1A[j]=0A[j]=0인 한 쌍의 항목으로, i\ltji\ltj입니다. 예를 들어, 0의 블록 다음에 1의 블록이 있는 배열에는 역전이 없으며, XX의 1이 뒤따르는 YY의 0의 블록이 있는 배열은 XYXY의 역전을 가지게 됩니다.

지나가는 선생님이 우연히 게임하는 두 사람을 발견했고, 게임이 동점인 것처럼 보이게 하기 위해 필요한 인접한 요소 사이에 최소 교환 횟수를 알고 싶어합니다.

💻 입력

입력의 첫 번째 줄에는 NN이 주어지고, 다음 줄에는 0 또는 1인 2N2N개의 정수가 주어집니다.

🖨️ 출력

게임이 비길 수 있는 인접한 교환 횟수를 적어주세요.


💻 예제 입력 1
5
0 0 0 1 0 1 0 0 0 1
🖨️ 예제 출력 1
1

💡 힌트

이 예에서, 배열의 첫 절반은 처음에 1번의 역전을 가지고 있고, 두 번째 절반은 3번의 역전을 가지고 있습니다. 55번째와 66번째 비트를 서로 교환하면 두 하위 배열 모두 역전이 00개가 됩니다.


출처: USACO 2019 US Open Contest, Gold Problem 3. Balancing Inversions