Nap Sort
플래티넘 I의견: 0
Bessie is trying to sort an array of integers using her own sorting algorithm.
She has a pile of \(N\) \((1 \leq N \leq 2\cdot 10^5)\) integers \(a_1,a_2,\dots,a_N\)
\((1 \leq a_i \leq 10^{11})\) that she will put in a separate array in sorted
order. She repeatedly finds the minimum integer in her pile, removes it, and
adds it to the end of the array. It takes Bessie \(p\) seconds to find the minimum
integer in a pile of \(p\) integers.
Farmer John instructed some of the other cows in the farm to help Bessie with
her task, but they are quite lazy, so Bessie uses that to her advantage. She
divides the integers into two piles: Bessie pile and Helper pile. For every
integer in Bessie's pile, she performs her algorithm as normal. For every
integer in the helper pile, she assigns it to a different helper cow. Farmer
John has a large farm, so Bessie can get as many helper cows as she wants. If a
helper receives the integer \(a_i\), Bessie instructs that cow to nap for \(a_i\)
seconds, and add their integer to the end of the array immediately when they
wake up. If Bessie and a helper add an integer to the array at the same time,
Bessie's integer will get added first since she is the leader. If more than one
helper gets assigned the same integer, they will add copies of that integer to
the array at the same time.
Help Bessie divide her integers so that the final array is sorted and the time
it takes to sort the array is minimized.
Problem credits: Suhas Nagar
SCORING
- Input 2: \(N\le 16\)
- Inputs 3-5: \(N\le 150\)
- Inputs 6-8: \(\sum N\le 5000\)
- Inputs 9-11: No additional constraints.
Problem credits: Suhas Nagar
The first line contains \(T\), the number of independent test cases
(\(1\le T\le 10\)).
Each test case is formatted as follows:
The first line of each test case contains the number of integers \(N\) in Bessie's
array.
The next line of each test case contains \(a_1, a_2, \dots, a_N\), the integers
that Bessie is sorting. The same integer may appear multiple times.
It is guaranteed that the sum of \(N\) over all tests does not exceed
\(2\cdot 10^5\).
For each test case, output the minimum time to sort the array on a new line, if
Bessie divides her integers optimally.
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
평가 및 의견
Nap Sort
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Nap Sort