레이팅 미적용설명
베시와 엘시는 길이 \(2N\)인 불리언 배열 \(A\) (\(1 \leq N \leq 10^5\)) 위에서 게임을 하고 있었다. 베시의 점수는 \(A\)의 앞쪽 절반에 있는 역위(inversion)의 수이고, 엘시의 점수는 \(A\)의 뒤쪽 절반에 있는 역위의 수였다. 역위란 \(i
농부 존이 우연히 게임판을 발견했는데, 게임이 무승부처럼 보이게 만들기 위해 필요한 인접 원소 간 교환의 최소 횟수가 궁금해졌다. 농부 존이 이 질문의 답을 알아내는 것을 도와주자.
문제 제공: Dhruv Rohatgi
제약
문제 제공: Dhruv Rohatgi
입력 형식
첫째 줄에 \(N\)이 주어지고, 다음 줄에 0 또는 1인 \(2N\)개의 정수가 주어진다.
출력 형식
게임을 무승부로 만들기 위해 필요한 인접 교환의 횟수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
balance.in · 출력을 쓸 파일 balance.out예제 1
입력
5
0 0 0 1 0 1 0 0 0 1출력
1설명
In this example, the first half of the array initially has \(1\) inversion, and
the second half has \(3\) inversions. After swapping the \(5\)th and \(6\)th bits with
each other, both subarrays have \(0\) inversions.
문제 정보
태그