레이팅 미적용소 베시는 최근 대면 수업으로 돌아오게 되어 신이 났다! 안타깝게도 담당 강사인 농부 존의 강의가 너무 지루해서, 베시는 수업 중에 자주 잠들고 만다.
농부 존은 베시가 수업에 집중하지 않는다는 것을 눈치챘다. 그는 같은 수업을 듣는 다른 학생 엘시에게 베시가 각 수업에서 몇 번 잠드는지 기록해 달라고 부탁했다. 수업은 총 \(N\) (\(1\le N\le 10^5\))교시이며, 엘시는 베시가 \(i\)번째 수업에서 \(a_i\) (\(0\le a_i\le 10^6\))번 잠들었다고 기록한다. 모든 수업에 걸쳐 베시가 잠든 총 횟수는 최대 \(10^6\)이다.
베시에게 강한 경쟁심을 느끼는 엘시는, 베시가 매 수업마다 똑같은 횟수로 꾸준히 잠드는 것처럼 농부 존이 느끼게 만들고 싶다. 그렇게 하면 문제가 전적으로 베시의 잘못이며, 농부 존의 가끔 지루한 강의와는 무관한 것처럼 보이게 할 수 있다. 엘시가 기록을 수정할 수 있는 유일한 방법은 인접한 두 수업을 하나로 합치는 것뿐이다. 예를 들어 \(a=[1,2,3,4,5]\)일 때 엘시가 두 번째와 세 번째 수업을 합치면 기록은 \([1,5,4,5]\)가 된다.
엘시가 기록의 모든 수를 같게 만들기 위해 필요한 최소 수정 횟수를 계산하도록 도와주자.
출제자: Jesse Choe
출제자: Jesse Choe
각 입력은 독립적으로 해결해야 하는 \(T\) (\(1\le T\le 10\))개의 테스트 케이스를 포함한다.
첫째 줄에 풀어야 할 테스트 케이스의 수 \(T\)가 주어진다. 이어서 \(T\)개의 테스트 케이스가 각각 두 줄로 주어진다. 각 쌍의 첫째 줄에 \(N\)이 주어지고, 둘째 줄에 \(a_1,a_2,\ldots,a_N\)이 주어진다.
각 테스트 케이스에서 \(a\)의 모든 값의 합이 최대 \(10^6\)임이 보장된다. 또한 모든 테스트 케이스에 대한 \(N\)의 합이 최대 \(10^5\)임이 보장된다.
\(T\)개의 줄에 걸쳐, 각 케이스에 대해 엘시가 기록의 모든 항목을 같게 만들기 위해 수행할 수 있는 최소 수정 횟수를 출력한다.
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 03
2
0For the first test case in this example, Elsie can change her log to consist
solely of 3s with 3 modifications.
1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
For the second test case, Elsie can change her log to 7 with 2 modifications.
2 2 3
-> 2 5
-> 7
For the last test case, Elsie doesn’t need to perform any operations; the log
already consists of equal entries.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Bronze