Sắp xếp ghế rạp chiếu phim (bản khó)

Điểm: 5,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một rạp chiếu phim có $n$ hàng ghế, mỗi hàng có $m$ ghế. Các ghế được đánh số từ $1$ đến $n m$ theo thứ tự: hàng $k$ chứa các ghế có chỉ số từ $m (k - 1) + 1$ đến $m k$ (đánh từ trái sang phải).

Có $n m$ người (đánh số từ $1$ đến $n m$ ) cùng vào xem phim. Người thứ $i$ có độ thị lực $a_{i}$ . Mỗi người được xếp đúng một ghế; gọi $s_{i}$ là chỉ số ghế xếp cho người $i$ . Phải xếp sao cho người có thị lực kém hơn được ghế có chỉ số nhỏ hơn, tức là với mọi cặp $i, j$ mà $a_{i} < a_{j}$ thì $s_{i} < s_{j}$ (nếu $a_{i} = a_{j}$ thì $s_{i}, s_{j}$ tùy ý).

Sau khi xếp chỗ xong, lần lượt theo thứ tự $1, 2, \dots, n m$ , từng người sẽ đi vào hàng chứa ghế của mình và đi từ ghế đầu hàng (trái nhất) tới ghế của mình. Trên đường đi, một số ghế có thể đã có người ngồi. Độ bất tiện của một người bằng số ghế đã có người ngồi mà người đó phải đi qua trước khi tới ghế của mình.

Hãy xếp chỗ để tổng độ bất tiện của tất cả $n m$ người là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 100$ ) — số test.

Với mỗi test:

Dòng thứ nhất chứa hai số nguyên $n, m$ ( $1 \leq n, m \leq 300$ ).
Dòng thứ hai chứa $n \cdot m$ số nguyên $a_{1}, a_{2}, \dots, a_{n m}$ ( $1 \leq a_{i} \leq 10^{9}$ ).

Tổng $n \cdot m$ trên tất cả các test không vượt quá $10^{5}$ .

Dữ liệu ra

Với mỗi test, in ra một số nguyên là tổng độ bất tiện nhỏ nhất có thể đạt được.

Ràng buộc

$1 \leq t \leq 100$
$1 \leq n, m \leq 300$
$1 \leq a_{i} \leq 10^{9}$
Tổng $n \cdot m \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
7 1 2 1 2 3 2 1 1 2 2 3 3 3 3 3 4 4 1 1 1 1 1 2 2 2 1 1 2 1 4 2 50 50 50 50 3 50 50 50 4 2 6 6 6 6 2 2 9 6 2 9 1 3 3 3 3 3 1 1 3 1 3 1 1 3 3 1 1 3	1 0 4 0 0 0 1	Test 1: chỉ có một cách xếp; người 1 ngồi ghế 1, người 2 ngồi ghế 2, độ bất tiện là 1. Test 2: do có nhiều người trùng thị lực, có thể xếp sao cho không ai phải đi qua người khác.
2 1 1 5 2 3 1 2 3 1 2 3	0 2	Test 1: chỉ có 1 ghế nên độ bất tiện bằng 0. Test 2: xếp tối ưu sẽ có tổng độ bất tiện 2.

Bình luận

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