Min max

Nguồn: CLUE OJ Độ khó: Dễ Vòng lặp Tìm lớn nhất

Đề bài

Cho dãy gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$. Hãy tìm số lớn nhất và số bé nhất trong dãy.

Dữ liệu vào:

• Dòng 1: số nguyên dương $n$.
• Dòng 2: $n$ số nguyên $a_1, a_2, \ldots, a_n$ cách nhau bởi dấu cách.

Kết quả:

Gồm hai dòng:

• Dòng 1: SO LON NHAT: x với $x$ là số lớn nhất của dãy.
• Dòng 2: SO BE NHAT: y với $y$ là số bé nhất của dãy.

Giới hạn:

• $1 \le n \le 10\,000$
• $-10^9 \le a_i \le 10^9$ (dãy có thể chứa số âm)

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
1 2 3 4 5

Ví dụ 1 – output

SO LON NHAT: 5
SO BE NHAT: 1

Ví dụ 2 – input

4
-3 -1 -8 -2

Ví dụ 2 – output

SO LON NHAT: -1
SO BE NHAT: -8

• Ví dụ 1: số lớn nhất là $5$, số bé nhất là $1$.
• Ví dụ 2: mọi số đều âm; số lớn nhất là $-1$, số bé nhất là $-8$.

Nguồn: phỏng theo bài "MIN MAX" – vinhdinhcoder.net (chủ đề Lặp FOR).

Lời mở đầu

Bài "Số lớn nhất" ở chương rẽ nhánh chỉ có 3 số, giờ là cả một dãy tới $10\,000$ số – không thể viết $10\,000$ câu if, nên ta dùng vòng lặp với mẫu quen thuộc "giả sử – cập nhật". Cái bẫy chính nằm ở giá trị khởi tạo: dãy có thể toàn số âm hoặc toàn số dương. Ghi chú: đề gốc cho $0 \le n$, nhưng với $n = 0$ thì không có số lớn nhất / bé nhất nên mình sửa thành $1 \le n$; đề gốc cũng chưa có giới hạn giá trị, mình bổ sung $|a_i| \le 10^9$ (có số âm).

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ưởnggiả sử – cập nhậtLờ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 n \le 10\,000$ và $|a_i| \le 10^9$.

Test	Nội dung kiểm tra
1–8	Dãy nhỏ: ví dụ đề, $n = 1$, dãy giảm dần, toàn số âm, toàn số dương, toàn số 0, có số trùng nhau
9–10, 16	Giá trị biên $\pm 10^9$, dãy chỉ có một số
11–12	$10\,000$ số toàn âm / toàn dương
13–15, 18–20	Số bé nhất / lớn nhất nằm ở đầu hoặc cuối dãy
17	$10\,000$ số ngẫu nhiên

Ý tưởngGiả sử số đầu tiên vừa lớn nhất vừa bé nhất

Đọc số đầu tiên $x$ và gán luôn mx = mn = x. Sau đó dùng vòng lặp đọc lần lượt $n - 1$ số còn lại, mỗi số $x$:

• nếu $x > mx$ thì mx = x (gặp số lớn hơn);
• nếu $x < mn$ thì mn = x (gặp số bé hơn).

Khi vòng lặp kết thúc, mx và mn chính là số lớn nhất và bé nhất. Ta không cần lưu cả dãy – đọc tới đâu so sánh tới đó.

Vì sao không khởi tạo mx = 0?

Nếu dãy toàn số âm (ví dụ 2: $-3, -1, -8, -2$) thì không số nào lớn hơn $0$, mx giữ nguyên $0$ – một số không hề có trong dãy! Tương tự mn = 0 sai khi dãy toàn số dương. Khởi tạo bằng chính số đầu tiên thì luôn đúng.

Em nhập dãy số (cách nhau bởi dấu cách) rồi bấm Tiếp để xem vòng lặp xét từng số:

Dãy số =

Ví dụ nhanh:

Lời giảiMột vòng lặp, hai câu if

Đọc số đầu tiên riêng để khởi tạo, rồi vòng lặp for đọc $n - 1$ số còn lại. Không cần mảng.

C++▶ Chạy tay từng dòng codeKhởi tạo bằng số đầu tiên, rồi đọc từng số và cập nhật mx, mn.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khi dãy dài hơn 15 số, phần còn lại được "tua nhanh" trong một bước cho gọn.

1. Hai câu if độc lập (không dùng else if) cho dễ hiểu. Với cách khởi tạo bằng số đầu tiên thì else if cũng đúng, nhưng nếu khởi tạo bằng "số rất lớn / rất bé" thì else if sẽ sai – xem phần bẫy.
2. $|a_i| \le 10^9$ vừa trong giới hạn int nên không cần long long.
3. Python: for x in map(int, input().split()) duyệt lần lượt từng số trên dòng 2; biến dem giúp nhận ra số đầu tiên.

Không gian$O(1)$

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.008s. Bản Python đúng 20/20 test, chạy lâu nhất 0.042s. 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ú
Khởi tạo mx = 0	16/20	sai test 2, 4, 10, 11
Khởi tạo mn = 0	14/20	sai test 1, 3, 5, 12, 16, 20
Khởi tạo mx = INT_MIN, mn = INT_MAX rồi dùng if … else if	15/20	sai test 1, 2, 13, 16, 19
Vòng lặp for(i = 1; i < n; i++) – chỉ đọc $n - 1$ số	10/20	sai test 1, 2, 3, 5, 8, 9, 14, 15, 16, 19

Vì sao else if lại sai?

Với mx = INT_MIN, số đầu tiên luôn lớn hơn mx nên chạy vào nhánh if – nhánh else if cập nhật mn bị bỏ qua. Nếu số đầu tiên chính là số bé nhất (hoặc dãy chỉ có 1 số) thì mn không bao giờ nhận được nó.

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.008s	Full điểm
	Python	20/20	0.042s	Full điểm
mx = 0	C++	16/20	–	Mất 4 test
mn = 0	C++	14/20	–	Mất 6 test
else if + INT_MIN/MAX	C++	15/20	–	Mất 5 test
Thiếu 1 số	C++	10/20	–	Mất 10 test

Ghi chú của mình: mẫu "khởi tạo bằng phần tử đầu tiên rồi cập nhật" là mẫu chuẩn để tìm lớn nhất / bé nhất – an toàn với mọi dãy, kể cả toàn số âm.

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 😇