레이팅 미적용베시는 자신만의 정렬 알고리즘으로 정수 배열을 정렬하려 한다. 베시에게는 \(N\) \((1 \leq N \leq 2\cdot 10^5)\)개의 정수 \(a_1,a_2,\dots,a_N\) \((1 \leq a_i \leq 10^{11})\)로 이루어진 더미가 있고, 이를 별도의 배열에 정렬된 순서로 넣으려 한다. 베시는 더미에서 최솟값을 찾아 제거하고 배열의 끝에 추가하는 일을 반복한다. \(p\)개의 정수가 있는 더미에서 최솟값을 찾는 데는 \(p\)초가 걸린다.
농부 존은 농장의 다른 소들에게 베시의 작업을 도우라고 지시했지만, 그 소들은 꽤 게을러서 베시는 이를 역이용하기로 했다. 베시는 정수들을 두 더미로 나눈다: 베시 더미와 도우미 더미. 베시 더미의 정수에 대해서는 평소대로 자신의 알고리즘을 수행한다. 도우미 더미의 각 정수는 서로 다른 도우미 소에게 배정한다. 농부 존의 농장은 커서 베시는 원하는 만큼 도우미 소를 부를 수 있다. 도우미가 정수 \(a_i\)를 받으면, 베시는 그 소에게 \(a_i\)초 동안 낮잠을 자고 깨어나는 즉시 자기 정수를 배열 끝에 추가하라고 지시한다. 베시와 도우미가 동시에 정수를 배열에 추가하면, 베시가 대장이므로 베시의 정수가 먼저 추가된다. 여러 도우미가 같은 정수를 배정받으면 그 정수의 복사본들이 동시에 배열에 추가된다.
최종 배열이 정렬되어 있으면서 배열을 정렬하는 데 걸리는 시간이 최소가 되도록 베시가 정수들을 나누는 것을 도와주자.
출제: Suhas Nagar
배점
- 입력 2: \(N\le 16\)
- 입력 3-5: \(N\le 150\)
- 입력 6-8: \(\sum N\le 5000\)
- 입력 9-11: 추가 제약 없음.
출제: Suhas Nagar
첫째 줄에 독립적인 테스트 케이스의 개수 \(T\)가 주어진다 (\(1\le T\le 10\)).
각 테스트 케이스는 다음과 같이 주어진다.
각 테스트 케이스의 첫째 줄에 베시의 배열에 있는 정수의 개수 \(N\)이 주어진다.
다음 줄에 베시가 정렬할 정수 \(a_1, a_2, \dots, a_N\)이 주어진다. 같은 정수가 여러 번 나타날 수 있다.
모든 테스트에 대한 \(N\)의 합이 \(2\cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트 케이스마다, 베시가 정수들을 최적으로 나눌 때 배열을 정렬하는 최소 시간을 새 줄에 출력한다.
4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 56
15
5
6In the first example, Bessie can assign \(1,2\) to helpers and leave \(4,5,10^{11}\)
for herself.
Time | Event
-----+----------------------
1 | Helper adds 1
2 | Helper adds 2
3 | Bessie adds 4
5 | Bessie adds 5
6 | Bessie adds 10^{11}
In the second example, the best Bessie can do is sort everything by herself. One
division that does not work is for Bessie to assign \(4\) to a helper and the
rest to herself because Bessie will end up adding \(17\) to the array before the
helper adds \(4\) to the array.
In the third example, Bessie can assign all the integers to helpers.
In the fourth example, Bessie can assign \(1,4,5\) to helpers and leave \(2,5,100\)
to herself.
Time | Event
-----+------------------
1 | Helper adds 1
3 | Bessie adds 2
4 | Helper adds 4
5 | Bessie adds 5
5 | Helper adds 5
6 | Bessie adds 100