Dãy Số 1 – Hiệu Số (HISO)
Đề bài
HISO – Hiệu số
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Cho một dãy $n$ số nguyên $a_1, a_2, \ldots, a_n$. Hãy tìm hai chỉ số $i, j$ sao cho $i \lt j$ và hiệu $a_j - a_i$ là lớn nhất.
Dữ liệu vào: gồm 2 dòng
- Dòng 1: là số nguyên $n$ $(2 \le n \le 10^5)$.
- Dòng 2: gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^9)$.
Dữ liệu xuất: Là giá trị lớn nhất của hiệu $a_j - a_i$.
3
1 2 324
2 5 1 33Lời mở đầu
Bài này thuộc dạng "nhập môn" nhưng lại là một ví dụ cực kỳ hay để các bạn thấy được cái hay của giải thuật: từ cách làm vét cạn $O(N^2)$ ai cũng nghĩ ra, chỉ cần một nhận xét nhỏ là rút xuống $O(N)$, rồi tối ưu thêm chút nữa thì bộ nhớ cũng chỉ còn $O(1)$ 😎. Mình sẽ đi lần lượt từng bước để các bạn thấy được cách tư duy từ cái dở của cách cũ mà nghĩ ra cách mới nhé.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Điều kiện quan trọng là $i \lt j$: số bị trừ $a_j$ phải đứng sau số trừ $a_i$ trong dãy, chứ không phải lấy số lớn nhất trừ số nhỏ nhất là xong đâu nha.
- Ví dụ 1: dãy
1 2 3, lấy $a_3 - a_1 = 3 - 1 = 2$ là lớn nhất. - Ví dụ 2: dãy
2 5 1 3. Nếu chỉ lấy "lớn nhất trừ nhỏ nhất" thì sẽ là $5 - 1 = 4$, nhưng số 1 lại đứng sau số 5 nên không được. Các cặp hợp lệ: $5-2=3$, $1-2=-1$, $3-2=1$, $1-5=-4$, $3-5=-2$, $3-1=2$ ⇒ lớn nhất là $\mathbf{3}$ (cặp $a_2 - a_1 = 5 - 2$).
5 3 1, thì mọi hiệu $a_j - a_i$ đều âm và đáp án là $-2$ (cặp $3 - 5$ hoặc $1 - 3$). Đề không hề nói đáp án không âm, nên khi khởi tạo biến lưu kết quả các bạn đừng khởi tạo bằng 0 nhé.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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn mọi cặp (i, j) – O(N²)
Một cách làm cơ bản nhất dễ dàng nhìn ra đó là vét cạn: xét hết tất cả các cặp $(i, j)$ thoả mãn $i \lt j$, tính hiệu $a_j - a_i$ và liên tục so sánh để sau cùng tìm ra hiệu lớn nhất.
Xem index bắt đầu từ 0, ta lần lượt xét $j = 1$ và $i$ là tất cả những thằng đứng trước $j$. Lý do $j$ bắt đầu từ 1 là vì nếu chọn $j = 0$ thì trước đó chẳng có thằng nào cả. Cứ thế $j$++ đến hết mảng, với mỗi giá trị $j$ thì vòng lặp for i sẽ duyệt các giá trị $i$ từ $j - 1$ về $0$. Ví dụ với $N = 5$ ta có các cặp $\{j, i\}$ sau:
j = 2, i = 1, 0 ⇒ {2, 1}, {2, 0}
j = 3, i = 2, 1, 0 ⇒ {3, 2}, {3, 1}, {3, 0}
j = 4, i = 3, 2, 1, 0 ⇒ {4, 3}, {4, 2}, {4, 1}, {4, 0}
Với mỗi cặp ta tính $a_j - a_i$ rồi so sánh qua tất cả các cặp để tìm ra hiệu lớn nhất, đó chính là đáp án.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
int Max = INT_MIN;
for(int j = 1; j < n; ++j){
for(int i = j - 1; i >= 0; --i){
Max = max(Max, a[j] - a[i]);
}
}
cout << Max;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = [int(x) for x in data[1:n + 1]]
Max = -float('inf')
for j in range(1, n):
for i in range(j - 1, -1, -1):
Max = max(Max, a[j] - a[i])
print(Max)Giải thích một số chỗ trong code ở trên:
- 2 dòng đầu tiên của hàm main (
ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất dữ liệu khi code C++ (các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé). Kinh nghiệm là bài nào cần nhập xuất nhiều, như bài này có tới $10^5$ số cần nhập, thì nên thêm 2 dòng này vào đầu hàm main để chương trình chạy nhanh hơn. - Biến
Maxkhởi tạo làINT_MIN, tức giá trị nhỏ nhất của kiểuint($-2{,}147{,}483{,}648$), để đảm bảo giá trị đầu tiên đem so sánh luôn lớn hơn nó mà cập nhật lạiMax. (Đây cũng là lý do mình nhắc ở trên: đáp án có thể âm nên không khởi tạo bằng 0.) - Câu lệnh
Max = max(Max, a[j] - a[i]);là cách viết gọn củaif(a[j] - a[i] > Max) Max = a[j] - a[i];. Hàmmax(a, b)trả về giá trị lớn hơn trong 2 giá trị, được hỗ trợ sẵn trong C++. Tương tự ta có hàmmin, về sau gặp thì các bạn cũng hiểu hen.
Các bạn bấm Tiếp ▶ trong khung bên dưới để xem từng cặp được xét như thế nào nhé:
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ với $N$ là số phần tử của mảng.
- Thời gian: $O(N)$ cho bước đọc mảng, cộng với số cặp cần xét là $1 + 2 + \ldots + (N-1) = \dfrac{N(N-1)}{2} = \dfrac{N^2}{2} - \dfrac{N}{2}$. Theo quy tắc cộng Big-O ta chỉ giữ thành phần lớn nhất là $\dfrac{N^2}{2} = 0.5 \cdot N^2$, theo quy tắc nhân Big-O thì bỏ hằng số $0.5$ ⇒ $O(N^2)$. Tổng lại $O(N) + O(N^2)$ thì lấy thành phần lớn nhất ⇒ $O(N^2)$.
Cách 2Nhớ giá trị nhỏ nhất phía trước – O(N)
Giờ ta đi bàn cách làm tối ưu. Cách vét cạn ở trên có cái dở là nó luôn phải xét đi xét lại những vị trí mà trước đó nó đã xét. Nhìn lại danh sách cặp khi $N = 5$:
j = 2 ⇒ {2, 1}, {2, 0}
j = 3 ⇒ {3, 2}, {3, 1}, {3, 0}
j = 4 ⇒ {4, 3}, {4, 2}, {4, 1}, {4, 0}
Vị trí $i = 0$ bị xét lặp lại đủ 4 lần, $i = 1$ bị xét lại 3 lần, $i = 2$ bị xét lại 2 lần. Đó chính là chỗ chưa tối ưu. Nếu mỗi vị trí $i$ chỉ cần xét qua đúng 1 lần thì sẽ nhanh hơn rất nhiều, các bạn đồng ý chứ?
Vậy vì sao cách trên lại cứ phải xét lại các vị trí $i$? Vì khi sang vị trí $j$ mới, nó muốn đảm bảo đã thử $a_j$ trừ cho tất cả các phần tử đứng trước để tìm hiệu lớn nhất. Nhưng khoan đã: muốn $a_j - a_i$ lớn nhất (với $a_j$ cố định) thì $a_i$ phải nhỏ nhất, vì trừ cho số nhỏ nhất thì kết quả sẽ lớn nhất, đây là quy luật toán học cơ bản!
- $Max = \max(Max,\ a_j - Min)$ (thử $a_j$ làm số bị trừ);
- $Min = \min(Min,\ a_j)$ (sau đó $a_j$ trở thành "phần tử phía trước" của các $j$ sau).
Dữ liệu đảm bảo mảng có tối thiểu 2 phần tử, nên ta khởi tạo $Min = \min(a_0, a_1)$ và $Max = a_1 - a_0$ (chính là cặp duy nhất khi $j = 1$), rồi duyệt tiếp từ index 2. Xét hết các $j$ thì đáp án chính là $Max$.
Minh hoạ: quét một lượt, mang theo Min
Các bạn nhập dãy số rồi bấm Tiếp để xem $Min$ (xanh dương) và $Max$ thay đổi ra sao khi $j$ (cam) chạy từ trái sang phải. Viền xanh lá là cặp đang cho hiệu lớn nhất:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
int Min = min(a[0], a[1]), Max = a[1] - a[0];
for(int j = 2; j < n; ++j){
Max = max(Max, a[j] - Min);
Min = min(Min, a[j]);
}
cout << Max;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = [int(x) for x in data[1:n + 1]]
Min = min(a[0], a[1])
Max = a[1] - a[0]
for j in range(2, n):
Max = max(Max, a[j] - Min)
Min = min(Min, a[j])
print(Max)Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ vì vẫn lưu cả mảng.
- Thời gian: $O(N)$ cho bước đọc mảng + $O(N)$ cho bước duyệt cập nhật $Min$, $Max$ ⇒ $O(2 \cdot N)$, bỏ hằng số ⇒ $O(N)$. Với $N = 10^5$ thì thấp hơn rất nhiều so với ngưỡng $10^8$, yên tâm không TLE.
int (tối đa khoảng $2.1 \cdot 10^9$). Nên dùng int ở bài này là an toàn.Cách 3Không cần mảng – O(N) thời gian, O(1) bộ nhớ
Thực ra ta còn tối ưu được nữa cả về không gian lẫn thời gian. Các bạn nhìn xem: vòng for đầu tiên duyệt từ đầu đến cuối để đọc dữ liệu vào mảng, rồi vòng for thứ 2 lại duyệt lại mảng từ đầu đến cuối. Vậy sao không gộp làm 1: đọc tới đâu xử lý tới đó?
Thêm nữa, khi xét $a_j$ thì nó chỉ cần so sánh với 2 biến $Min$, $Max$ rồi cập nhật lại, hoàn toàn không cần nhìn lại các phần tử trước đó. Vậy cũng chẳng cần lưu mảng làm gì, ta chỉ cần một biến $x$ đại diện: đọc vào $x$ rồi đem $x$ đi so sánh, cập nhật $Min$, $Max$.
cin >> n >> Min >> x;: đọc $a_0$ thẳng vàoMin, đọc $a_1$ vàox.Max = x - Min;chính là $Max = a_1 - a_0$.Min = min(Min, x);chính là $Min = \min(a_0, a_1)$.- Vòng
forbắt đầu từ phần tử thứ 3 (i = 2), mỗi lần đọc vàox, lúc nàyxđóng vai trò $a_j$ của code trước. Mọi thứ đều y hệt, các bạn thấy không?
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, x, Min, Max;
cin >> n >> Min >> x;
Max = x - Min;
Min = min(Min, x);
for(int i = 2; i < n; ++i){
cin >> x;
Max = max(Max, x - Min);
Min = min(Min, x);
}
cout << Max;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
Min = int(data[1])
x = int(data[2])
Max = x - Min
Min = min(Min, x)
for i in range(2, n):
x = int(data[i + 1])
if x - Min > Max:
Max = x - Min
if x < Min:
Min = x
print(Max)Đánh giá độ phức tạp của cách làm này:
- Không gian: không dùng mảng, chỉ vài biến ⇒ $O(1)$.
- Thời gian: về lý thuyết vẫn là $O(N)$, nhưng thực tế nhanh hơn code trước vì chỉ cần 1 vòng lặp qua $N$ phần tử thay vì 2 vòng (code trước xét đúng thực tế là $O(2 \cdot N)$, còn code này chỉ $O(N)$). Tổng quát thì cả 2 đều kết luận là $O(N)$.
Đến đây các bạn đã thấy cái hay của giải thuật rồi chứ? Thời gian từ $O(N^2)$ rút xuống chỉ còn $O(N)$, không gian từ $O(N)$ rút xuống chỉ còn $O(1)$ hehe 😆
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét