#PU1379. USACO 2024 January Contest, Gold — Problem 3. Nap Sort

    ID: 1550 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan24来源:usaco.orgscoring:equal_test_cases排序分治

USACO 2024 January Contest, Gold — Problem 3. Nap Sort

USACO 2024 January Contest, Gold — Problem 3. Nap Sort

题目描述

Bessie is trying to sort an array of integers using her own sorting algorithm. She has a pile of NN (1≤N≤2⋅105)(1 \leq N \leq 2\cdot 10^5) integers a1,a2,…,aNa_1,a_2,\dots,a_N (1≤ai≤1011)(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 pp seconds to find the minimum integer in a pile of pp 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 aia_i, Bessie instructs that cow to nap for aia_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.

输入格式

The first line contains TT, the number of independent test cases (1≤T≤101\le T\le 10). Each test case is formatted as follows: The first line of each test case contains the number of integers NN in Bessie's array. The next line of each test case contains a1,a2,…,aNa_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 NN over all tests does not exceed 2⋅1052\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.

数据范围

(见题面原文)

样例

样例 1

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5
6
15
5
6
In 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