Sắp Xếp Ngủ

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất, loại bỏ nó, và thêm vào mảng kết quả. Tìm phần tử nhỏ nhất trong đống $p$ số nguyên mất $p$ giây.

Bessie có thể chia các số nguyên giữa mình và các con bò trợ giúp:

Bessie xử lý đống của mình bình thường (mỗi lần rút mất thời gian bằng kích thước đống hiện tại).
Trợ giúp được giao một số nguyên thì sẽ ngủ đúng bằng giá trị số đó (tính bằng giây), rồi thêm nó vào mảng kết quả khi thức dậy.
Nếu Bessie và trợ giúp hoàn thành cùng lúc, phần tử của Bessie được thêm trước.

Hãy tìm thời gian tối thiểu để sắp xếp mảng bằng cách phân chia tối ưu.

Dữ liệu vào

Dòng đầu tiên: số nguyên $T$ ( $1 \leq T \leq 10$ ) - số test case.
Mỗi test case:
- Dòng 1: số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ ).
- Dòng 2: $N$ số nguyên $a_{1}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 10^{11}$ ).
Tổng $N$ qua tất cả test case $\leq 2 \times 10^{5}$ .

Dữ liệu ra

Với mỗi test case, in thời gian tối thiểu.

Ràng buộc

$1 \leq T \leq 10$
$1 \leq N \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq 10^{11}$

Ví dụ

Input	Output	Giải thích
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	Test 1: Bessie lấy {4,5,100000000000}, trợ giúp lấy {1,2}. Bessie xong sau 3+2+1=6 giây.

Bình luận

Không có bình luận tại thời điểm này.