Cặp đôi hoàn hảo

Nguồn: CLUE OJ Độ khó: Trung bình Mảng 1 chiều Mã bài VT13

Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử $A_0, A_1, \ldots, A_{n-1}$ được xếp thành vòng tròn: mỗi phần tử $A_i$ lân cận với $A_{i+1}$, và phần tử cuối $A_{n-1}$ lân cận với phần tử đầu $A_0$.

Ta có $n$ cặp lân cận: $(A_0, A_1), (A_1, A_2), \ldots, (A_{n-2}, A_{n-1})$ và $(A_{n-1}, A_0)$. Cặp thứ $i$ (bắt đầu tại chỉ số $i$) là $(A_i, A_{(i+1) \bmod n})$.

Hãy tìm cặp lân cận có tổng lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên $n$.
• Dòng thứ hai gồm $n$ số nguyên $A_0, A_1, \ldots, A_{n-1}$, cách nhau bởi dấu cách.

Kết quả:

In ra hai phần tử của cặp tìm được, cách nhau một dấu cách, theo đúng thứ tự của cặp: $A_i$ trước, $A_{(i+1) \bmod n}$ sau. Riêng cặp (phần tử cuối, phần tử đầu) thì in phần tử cuối trước.

Nếu có nhiều cặp cùng tổng lớn nhất, chọn cặp có chỉ số bắt đầu $i$ lớn hơn (cặp (cuối, đầu) có $i = n - 1$ là lớn nhất).

Giới hạn:

• $2 \le n \le 10^4$
• $|A_i| \le 10^8$

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

Ví dụ 1 – input

5
3 2 -1 2 4

Ví dụ 1 – output

4 3

Ví dụ 2 – input

6
1 2 6 1 6 2

Ví dụ 2 – output

6 2

Giải thích:

• Ví dụ 1: tổng các cặp là $5, 1, 1, 6$ và cặp (cuối, đầu) $4 + 3 = 7$ lớn nhất, in phần tử cuối trước: 4 3.
• Ví dụ 2: cặp $(2, 6)$ bắt đầu ở chỉ số $1$ và cặp $(6, 2)$ bắt đầu ở chỉ số $4$ cùng có tổng $8$; chọn chỉ số lớn hơn nên in 6 2.

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

Ý tưởng

Cặp thứ $i$ là (A[i], A[(i+1) % n]); với $i = n-1$ thì (i+1) % n = 0 nên ta có luôn cặp (cuối, đầu) và in đúng thứ tự "cuối trước". Duyệt $i$ từ 0 đến $n-1$ theo thứ tự tăng dần, khi tổng >= tổng tốt nhất thì cập nhật – dấu >= giúp khi hoà ta chọn chỉ số lớn hơn. Khởi tạo tổng tốt nhất bằng tổng cặp đầu tiên (không phải 0).

Ví dụ $1, 2, 6, 1, 6, 2$: tổng các cặp $3, 8, 7, 7, 8, 3$. Hai cặp tổng 8 ở $i = 1$ và $i = 4$, chọn $i = 4$ → 6 2.

Lưu ý / bẫy thường gặp

• Quên cặp vòng (phần tử cuối, phần tử đầu).
• Dùng > nên khi hoà lại chọn chỉ số nhỏ hơn.
• In cặp vòng theo thứ tự "đầu trước, cuối sau" – đề yêu cầu phần tử cuối trước.
• Khởi tạo tổng lớn nhất bằng 0: khi mọi tổng đều âm sẽ không cập nhật được.

Lời giải

Code chuẩn bên dưới đã chấm đúng toàn bộ 20 test trên CLUE OJ.

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 😇