Đổi chỗ lớn nhất và nhỏ nhất

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Tìm max – min

Đề bài

Cho số nguyên dương $N$ và dãy số nguyên $A_1, A_2, \ldots, A_N$ gồm $N$ phần tử đôi một khác nhau. Hãy đổi chỗ phần tử có giá trị lớn nhất và phần tử có giá trị nhỏ nhất cho nhau (các phần tử khác giữ nguyên vị trí), rồi in ra dãy $A$ sau khi đổi.

Dữ liệu vào:

• Dòng đầu là số nguyên dương $N$.
• Dòng thứ hai gồm $N$ số nguyên $A_1, A_2, \ldots, A_N$ đôi một khác nhau.

Kết quả:

In ra dãy $A$ sau khi đổi chỗ, các số cách nhau bởi dấu cách.

Giới hạn:

• $1 \le N < 10000$
• $|A_i| < 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

5
4 2 9 7 1

Ví dụ 1 – output

4 2 1 7 9

• Số lớn nhất là $9$ (vị trí 3), số nhỏ nhất là $1$ (vị trí 5). Đổi chỗ hai số này được $4, 2, 1, 7, 9$.
• Nếu $N = 1$ thì phần tử duy nhất vừa lớn nhất vừa nhỏ nhất, dãy giữ nguyên.

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

Lời mở đầu

Tìm số lớn nhất và số nhỏ nhất thì quen rồi, nhưng muốn đổi chỗ chúng thì phải biết chúng nằm ở đâu. Bài này luyện thói quen lưu vị trí (chỉ số) thay vì chỉ lưu giá trị.

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ưởnglưu vị trí max, minLờ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 đều có các phần tử đôi một khác nhau.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2–3	$N = 1$ (dãy giữ nguyên) và $N = 2$
4, 9, 14, 18	Toàn số âm – khởi tạo max = 0 là sai
10, 19	Toàn số dương – khởi tạo min = 0 là sai
5–7, 15, 17	Max/min nằm ở đầu hoặc cuối dãy, dãy tăng/giảm dần
8, 12–13, 18–20	Giá trị cỡ $10^{18}$, quanh $2^{31}$ và $\pm 5 \cdot 10^9$ – int bị tràn, khởi tạo $\pm 10^9$ bị sai
13–20	Dãy dài tới 9999 phần tử

Ý tưởngTìm vị trí max, vị trí min rồi đổi chỗ

Duyệt mảng một lần, dùng hai biến vtMax, vtMin lưu vị trí của số lớn nhất và nhỏ nhất đang biết. Ban đầu cả hai bằng 1 (coi phần tử đầu tiên vừa lớn nhất vừa nhỏ nhất). Gặp a[i] > a[vtMax] thì vtMax = i; gặp a[i] < a[vtMin] thì vtMin = i.

Duyệt xong, đổi chỗ a[vtMax] và a[vtMin] bằng một biến tạm.

Khởi tạo bằng phần tử đầu tiên

Nếu khởi tạo max = 0 thì với dãy toàn số âm sẽ không bao giờ tìm được max; khởi tạo max = -10^9 cũng sai vì $A_i$ có thể tới $-10^{18}$. Cách an toàn nhất là lấy luôn phần tử đầu tiên làm mốc.

Đổi chỗ cần biến tạm

a[x] = a[y]; a[y] = a[x]; làm mất giá trị cũ của a[x] – cả hai ô thành cùng một số. Phải cất a[x] vào biến tạm t trước.

Em nhập dãy rồi bấm Tiếp để xem chương trình dò vị trí lớn nhất, nhỏ nhất:

Dãy A =

Ví dụ nhanh:

Lời giảiMột vòng lặp tìm hai vị trí

Mảng khai báo kiểu long long vì $|A_i|$ tới $10^{18}$.

C++▶ Chạy tay từng dòng codeTìm vị trí max, min rồi đổi chỗ bằng biến tạm.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Hai câu if đặt riêng (không dùng else if giữa max và min cũng được) vì một phần tử không thể vừa lớn hơn max vừa nhỏ hơn min.
2. Khi $N = 1$ thì vtMax = vtMin = 1, phép đổi chỗ không làm gì – dãy giữ nguyên.
3. Python có thể đổi chỗ gọn: a[x], a[y] = a[y], a[x].

Không gian$O(N)$

Thời gian$O(N)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.005s. Bản Python đúng 20/20 test, chạy lâu nhất 0.040s. 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ú
Dùng int cho mảng	10/20	sai test 8, 9, 10, 12, 13, 15, 17, 18, 19, 20
Khởi tạo max = 0, min = 0	10/20	sai test 1, 4, 5, 7, 9, 10, 14, 15, 18, 19
Khởi tạo max = -1e9, min = 1e9	18/20	sai test 18, 19
Đổi chỗ không dùng biến tạm (a[y] = a[x]; a[x] = a[y];)	1/20	sai test 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 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.005s	Full điểm
	Python	20/20	0.040s	Full điểm
Dùng int	C++	10/20	–	Mất 10 test
max = min = 0	C++	10/20	–	Mất 10 test
Mốc ±1e9	C++	18/20	–	Mất 2 test
Thiếu biến tạm	C++	1/20	–	Mất 19 test

Ghi chú của mình: khi cần sửa phần tử tìm được (đổi chỗ, xoá, thay giá trị) thì hãy lưu vị trí của nó, không chỉ lưu giá trị.

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 😇