Số lớn nhất và vị trí của nó

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

Đề bài

Cho số nguyên dương $N$ và dãy số nguyên $A_1, A_2, \ldots, A_N$. Hãy tìm phần tử lớn nhất của dãy cùng vị trí của nó (vị trí đánh số từ $1$). Nếu có nhiều phần tử cùng có giá trị lớn nhất thì đáp án là phần tử có vị trí bé nhất.

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$.

Kết quả:

In ra hai số nguyên cách nhau bởi dấu cách: giá trị lớn nhất và vị trí của nó.

Giới hạn:

• $1 \le N < 10000$
• $|A_i| < 10^9$

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 12 -4 -3 12

Ví dụ 1 – output

12 2

Giá trị lớn nhất là $12$, xuất hiện ở vị trí 2 và 5; ta chọn vị trí bé nhất là 2.

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

Lời mở đầu

Tìm số lớn nhất kèm vị trí; nếu số lớn nhất xuất hiện nhiều lần thì lấy vị trí bé nhất. Bí quyết: chỉ cập nhật khi gặp số lớn hơn hẳn. Ghi chú: đề gốc viết "Nếu có nhiều phần tử cùng có giá trị nhỏ nhất thì đáp án là phần tử có vị trí bé nhất" – rõ ràng là gõ nhầm, vì bài hỏi số lớn nhất và ví dụ 1 12 -4 -3 12 → 12 2 lấy số 12 ở vị trí 2. Mình sửa thành "lớn nhất".

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ưởngcập nhật khi a[i] > maxLờ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.

Test	Nội dung kiểm tra
1	Ví dụ của đề (max xuất hiện 2 lần)
2, 4, 7–8, 12, 16–17, 19	Toàn số âm hoặc max bằng 0 – khởi tạo max = 0 là sai
3, 7, 9–10, 13–14, 19	Max xuất hiện nhiều lần – so sánh >= lấy nhầm vị trí cuối
5–6, 15, 18	Max ở cuối, ở đầu dãy, dãy tăng dần tới 9999 phần tử
11, 20	Dãy ngẫu nhiên, $N = 2$

Ý tưởngLưu vị trí, so sánh nghiêm ngặt

Biến vt lưu vị trí số lớn nhất đã gặp, khởi tạo vt = 1. Duyệt $i = 2..N$, nếu a[i] > a[vt] thì vt = i. Cuối cùng in a[vt] và vt.

> chứ không phải >=

Khi gặp một số bằng max hiện tại, ta không cập nhật – nên vt giữ nguyên vị trí xuất hiện đầu tiên. Nếu dùng >=, vt sẽ nhảy tới lần xuất hiện cuối cùng.

Em nhập dãy rồi bấm Tiếp:

Dãy A =

Ví dụ nhanh:

Lời giảiMột biến lưu vị trí

$|A_i| < 10^9$ nên int là đủ.

C++▶ Chạy tay từng dòng codeTìm vị trí lớn nhất, chỉ cập nhật khi lớn hơn hẳn.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Không cần biến max riêng: a[vt] chính là giá trị lớn nhất.
2. Python: duyệt chỉ số từ 0 và in vt + 1.

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.022s. 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 max = 0	12/20	sai test 2, 4, 7, 8, 12, 16, 17, 19
So sánh >= (ra vị trí cuối cùng)	10/20	sai test 1, 3, 4, 7, 9, 10, 13, 14, 16, 19
In vị trí đếm từ 0	0/20	sai test 1, 2, 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.022s	Full điểm
max = 0	C++	12/20	–	Mất 8 test
So sánh >=	C++	10/20	–	Mất 10 test
Vị trí từ 0	C++	0/20	–	Mất 20 test

Ghi chú của mình: "vị trí bé nhất" ⇔ so sánh >, "vị trí lớn nhất" ⇔ so sánh >=. Chỉ một dấu bằng mà khác hẳn đáp án.

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 😇