Sắp xếp từng dòng của ma trận

Nguồn: CLUE OJ Độ khó: Dễ Mảng 2 chiều Sắp xếp

Đề bài

Cho ma trận số nguyên $A$ gồm $m$ dòng và $n$ cột. Với mỗi dòng, hãy sắp xếp các số trong dòng đó theo thứ tự không giảm (các dòng được sắp xếp riêng, không đổi chỗ số giữa các dòng).

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương $m, n$.
• $m$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên là một dòng của ma trận $A$.

Kết quả:

In ra ma trận $A$ sau khi sắp xếp: $m$ dòng, mỗi dòng $n$ số cách nhau bởi dấu cách.

Giới hạn:

• $1 \le m, n \le 199$
• $|A[i][j]| < 10^{18}$

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

3 4
4 5 2 1
7 3 5 6
9 8 6 4

Ví dụ 1 – output

1 2 4 5
3 5 6 7
4 6 8 9

Nguồn: phỏng theo bài "MẢNG 6.7" – vinhdinhcoder.net (chủ đề Mảng 2 chiều).

Lời mở đầu

Mỗi dòng của ma trận a[i][...] thực chất là một mảng 1 chiều. Vì vậy sắp xếp từng dòng chỉ là gọi sort cho từng mảng con a[i]. Ghi chú: đề gốc ghi $0 < m, n < 200$, mình viết lại thành $1 \le m, n \le 199$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngsort(a[i], a[i] + n)Lời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test có $1 \le m, n \le 199$, $|A[i][j]| < 10^{18}$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–10	Ma trận nhỏ: 1 ô, một dòng, một cột, dòng đã tăng/giảm sẵn, số âm, số vượt int
11–20	Ma trận lớn tới 199 × 199 với số tới $10^{18}$

Ý tưởngMỗi dòng là một mảng 1 chiều

Trong C++, a[i] là địa chỉ đầu dòng i, các phần tử của dòng nằm liền nhau từ a[i][0] tới a[i][n − 1]. Vì vậy sort(a[i], a[i] + n) sắp xếp đúng dòng i mà không đụng tới các dòng khác.

Dòng nào ra dòng nấy

Đề chỉ yêu cầu sắp xếp trong từng dòng: dòng 0 sau khi sắp xếp vẫn gồm đúng các số của dòng 0. Không được gộp cả ma trận rồi sắp (đó là bài "Sắp xếp toàn bộ ma trận").

Em nhập ma trận (các dòng cách nhau bởi dấu ;) rồi bấm Tiếp:

Ma trận =

Ví dụ nhanh:

Lời giảiGọi sort cho từng dòng

Chỉ cần một vòng for qua các dòng; phần còn lại là đọc và in ma trận.

C++▶ Chạy tay từng dòng codeLần lượt sort(a[i], a[i] + n) cho từng dòng.

Dữ liệu vào (stdin) – sửa thoải mái3 4 4 5 2 1 7 3 5 6 9 8 6 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. a[i] và a[i] + n là hai "con trỏ" chỉ đầu và cuối đoạn cần sắp xếp của dòng i.
2. Không gọi sort(a[0], a[0] + m * n): lệnh đó (vì các dòng khai báo dài 205 ô) sẽ trộn cả các ô thừa của mảng.
3. Python: row.sort() cho từng danh sách dòng.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n \log n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.013s. Bản Python đúng 20/20 test, chạy lâu nhất 0.032s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Sắp xếp cả ma trận rồi chia lại theo dòng	4/20	sai test 1, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20
Dùng int	12/20	sai test 7, 9, 11, 14, 15, 16, 18, 20
Sắp xếp theo cột thay vì theo dòng	2/20	sai test 1, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Sắp xếp giảm dần	3/20	sai test 1, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.013s	Full điểm
	Python	20/20	0.032s	Full điểm
Sắp cả ma trận	C++	4/20	–	Mất 16 test
Dùng int	C++	12/20	–	Mất 8 test
Sắp theo cột	C++	2/20	–	Mất 18 test
Giảm dần	C++	3/20	–	Mất 17 test

Ghi chú của mình: "không giảm" nghĩa là số sau lớn hơn hoặc bằng số trước – chính là tăng dần khi cho phép trùng nhau.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇