Biến đổi mảng theo lân cận (VT08)

Nguồn: CLUE OJ Độ khó: Dễ Mảng 1 chiều Mã bài VT08

Đề bài

Cho mảng số nguyên $A$ gồm $n$ phần tử, chỉ số tính từ $0$: $A_0, A_1, \ldots, A_{n-1}$. Hãy biến đổi mảng theo quy tắc sau:

• Tại mỗi chỉ số lẻ $i$ ($i = 1, 3, 5, \ldots$), tăng $A_i$ thêm một lượng bằng chênh lệch (trị tuyệt đối của hiệu) giữa hai phần tử lân cận của nó: $A_i \leftarrow A_i + |A_{i-1} - A_{i+1}|$.
• Lân cận trái của $A_i$ là $A_{i-1}$, lân cận phải là $A_{i+1}$. Nếu không có lân cận phải ($i = n - 1$) thì coi lân cận đó bằng $0$.
• Các phần tử ở chỉ số chẵn giữ nguyên.

Dữ liệu vào:

• Dòng đầu tiên là số nguyên dương $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 mảng sau khi biến đổi trên một dòng, các phần tử cách nhau một dấu cách.

Giới hạn:

• $1 \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

4
1 3 2 5

Ví dụ 1 – output

1 4 2 7

Giải thích:

• Chỉ số $1$: hai lân cận là $1$ và $2$, chênh lệch $|1 - 2| = 1$, nên $3 \to 4$.
• Chỉ số $3$: lân cận trái là $2$, không có lân cận phải (coi là $0$), chênh lệch $|2 - 0| = 2$, nên $5 \to 7$.

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

Duyệt các chỉ số lẻ i = 1, 3, 5, ... (i += 2). Lân cận trái luôn có (A[i-1] vì $i \ge 1$); lân cận phải là A[i+1] nếu i + 1 < n, ngược lại là $0$. Cộng abs(trai - phai) vào A[i].

Vì chỉ sửa ở chỉ số lẻ, còn hai lân cận đều ở chỉ số chẵn (không bị sửa), nên có thể sửa trực tiếp trên mảng.

Ví dụ $1, 3, 2, 5$: $i = 1$: $3 + |1 - 2| = 4$; $i = 3$: $5 + |2 - 0| = 7$ → 1 4 2 7.

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

• Quên lấy trị tuyệt đối: "chênh lệch" luôn không âm.
• Dừng vòng lặp ở i + 1 < n nên bỏ qua phần tử cuối (chỉ số lẻ) không có lân cận phải – phần tử đó vẫn phải biến đổi với lân cận phải bằng 0.
• Nhầm chỉ số (biến đổi ở chỉ số chẵn) khi quen đếm từ 1.
• Cộng tổng hai lân cận thay vì chênh lệch.

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 😇