Tích Lớn Nhất (TICHMAX)
Đề bài
Cho một dãy gồm $N$ số nguyên. Hãy tìm 3 số trong dãy với tích $T$ của chúng là lớn nhất.
Dữ liệu vào từ file văn bản TICHMAX.INP gồm:
- Dòng đầu ghi số $N$ $(3 \le N \le 10000)$,
- Dòng thứ hai chứa $N$ số nguyên có giá trị tuyệt đối không vượt quá $30000$.
Kết quả ghi ra file văn bản TICHMAX.OUT một số nguyên duy nhất $T$.
Ví dụ: (khung trái là nội dung TICHMAX.INP, khung phải là nội dung TICHMAX.OUT)
9
3 5 1 7 9 0 9 -3 10810TICHMAX.INP / TICHMAX.OUT. Các code bên dưới dùng mẹo if (fopen("TICHMAX.INP", "r")) { freopen(...); freopen(...); } (Python: if os.path.exists("TICHMAX.INP")): có file thì đọc/ghi file, không có thì đọc bàn phím và in ra màn hình. Nhờ vậy cùng 1 code nộp được cả lên hệ thống chấm đọc từ bàn phím lẫn khi thi chấm bằng file.Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Các bạn nào muốn thử nộp bài để hệ thống chấm có đúng hay không thì link bài đây nha:
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJChỉ một bài này thôi nhưng mình sẽ giải theo 3 cách làm khác nhau với độ phức tạp tối ưu dần. Hi vọng anh em học được nhiều kiến thức.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngChỉ có 2 ứng viên cho đáp án
Tư tưởng giải quyết bài này rất dễ để nhìn ra đó là so sánh tích của 3 số trong 2 trường hợp dưới đây xem trường hợp nào cho kết quả lớn hơn thì đó chính là đáp án.
- Trường hợp 1: Tích của 3 số lớn nhất. Quá rõ ràng để hiểu vì sao lại như vậy? Ví dụ nếu mảng toàn số dương thì tích lớn nhất của 3 số bất kỳ chắc chắn phải là 3 số lớn nhất của mảng.
- Trường hợp 2: Vì trong bài này mảng có cả số âm nên ta phải tính đến tình huống 2 số âm nhân nhau thì kết quả sẽ được số dương. Và rõ ràng nếu 2 số âm bé nhất nhân nhau thì kết quả sẽ ra số dương lớn nhất. Thế nên lúc này ta phải tính tích của 2 số bé nhất của mảng và số lớn nhất của mảng.
Ta tính toán kết quả tích 3 số của 2 trường hợp nói trên rồi so sánh với nhau là ra đáp án. Lúc này nó chỉ đơn giản là:
T = max(lớn nhất × lớn nhì × lớn ba, bé nhất × bé nhì × lớn nhất)Về độ lớn: $|T| \le 30000^3 = 2.7 \cdot 10^{13}$, vượt xa giới hạn của int (khoảng $2.1 \cdot 10^9$) nên trong C++ phải dùng long long để nhân nhé.
Cách 1Sắp xếp mảng – O(N log N)
Vậy với tư tưởng để giải quyết ở trên thì cách code nhanh gọn nhất (nhưng bù lại độ phức tạp không phải tối ưu nhất) đó là đi sắp xếp mảng tăng dần, lúc này 3 số lớn nhất chính là 3 số cuối cùng của mảng, 2 số bé nhất chính là 2 số đầu tiên của mảng, rất nhanh chóng để tìm ra từ đó tính toán trả ra kết quả bài toán.
sort trong STL C++ để sắp xếp thì độ phức tạp sẽ được tối ưu, không nên tự code hàm sắp xếp vì vừa code dài mà độ phức tạp không được tối ưu. (Tất nhiên nếu bạn nào không biết hàm sort STL thì đành phải tự code hàm sort riêng. Với giới hạn $N \le 10^4$ của đề này thì kể cả sắp xếp $O(N^2)$ vẫn AC được, nhưng nếu số lượng phần tử nhiều hơn cỡ tầm $10^5$ trở lên thì thuật $O(N^2)$ sẽ bị TLE, lúc đó phải dùng những thuật $O(N \log N)$ mới chịu nổi nha.)Code giải quyết theo hướng sắp xếp ở trên cho anh em tham khảo:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
if (fopen("TICHMAX.INP", "r")) {
freopen("TICHMAX.INP", "r", stdin);
freopen("TICHMAX.OUT", "w", stdout);
}
int n;
cin >> n;
long long a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
cout << max(a[n-1] * a[n-2] * a[n-3], a[0] * a[1] * a[n-1]);
return 0;
}import sys, os
if os.path.exists("TICHMAX.INP"):
sys.stdin = open("TICHMAX.INP", "r")
sys.stdout = open("TICHMAX.OUT", "w")
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
res = max(a[-1] * a[-2] * a[-3], a[0] * a[1] * a[-1])
print(res)Đánh giá độ phức tạp:
- Thời gian: $O(N \log N)$ của bước sắp xếp + $O(N)$ của bước đọc mảng ban đầu ⇒ tổng quát là $O(N \log N)$ (theo quy tắc cộng Big-O lấy theo thằng lớn nhất).
- Không gian: $O(N)$ do tạo mảng lưu trữ $N$ phần tử.
Cách 2Duyệt 5 lần tìm từng số – O(N)
Theo cách ở trên thì độ phức tạp chưa phải là tối ưu nhất nhưng vẫn giải quyết được bài này. Nếu giả sử bài này đổi lại giới hạn $N$ tối đa có thể lên đến $10^7$ hay $10^8$ phần tử thì cách làm ở trên sẽ bị TLE (Time Limit Exceeded – chạy quá giới hạn thời gian cho phép). Lúc này nếu muốn AC được thì phải đưa ra giải thuật với độ phức tạp tối ưu hơn.
Bài này có thể giải quyết với độ phức tạp $O(N)$. Chúng ta không cần đi sắp xếp mà chỉ cần duyệt vòng lặp xét qua các phần tử của mảng là có thể tìm ra 3 số lớn nhất và 2 số nhỏ nhất. Bài toán tìm số lớn nhất, nhỏ nhất trong mảng là bài toán quá cơ bản rồi hen. Tuy nhiên vấn đề lúc này không phải chỉ tìm ra 1 số lớn nhất mà phải tìm đến 3 số lớn nhất, tương tự không phải chỉ tìm 1 số nhỏ nhất mà phải tìm đến 2 số nhỏ nhất.
Nếu chỗ này bạn nào code không vững thì sẽ đi theo hướng làm không được tốt lắm nhưng dễ để nhìn ra:
- Duyệt hết 1 vòng lặp tìm ra số lớn nhất, lưu vị trí số lớn nhất đó lại.
- Duyệt tiếp 1 vòng lặp xét các số ở các vị trí khác vị trí số lớn nhất đã tìm được ⇒ số lớn nhất trong các số này chính là số lớn nhì.
- Làm tương tự, duyệt vòng lặp xét tất cả các số ở các vị trí khác 2 vị trí đã tìm ra ⇒ số lớn nhất trong các số này là số lớn thứ ba.
- Tìm 2 số nhỏ nhất thì lại duyệt 2 vòng lặp nữa.
Vậy tổng cộng sẽ cần duyệt 5 lần vòng lặp để tìm ra 3 số lớn nhất và 2 số nhỏ nhất. Đây là hướng làm không tối ưu nhưng dễ để nhìn ra. Tuy bản chất máy tính sẽ đi thực hiện 5 lần vòng lặp nhưng nếu bạn nào biết cách dùng hàm để gọi lại thì sẽ code rất gọn: chỉ cần viết vòng lặp 1 lần trong hàm rồi gọi lại hàm thôi. Trong code dưới, số lớn nhất và nhỏ nhất được tìm luôn trong lúc đọc mảng, còn hàm FindMinOrMax bỏ qua các vị trí đã chọn (lưu trong x, y, z, truyền tham chiếu) và tự ghi vị trí mới tìm được vào ô còn trống. Mình cũng code thử theo hướng này cho anh em tham khảo:
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
long long FindMinOrMax(long long a[], int n, int &x, int &y, int &z, bool isMax) {
long long Max = LLONG_MIN, Min = LLONG_MAX;
int idx = -1;
for(int i = 0; i < n; i++) {
if(i != x && i != y && i != z) {
if(isMax == true && a[i] >= Max) {
Max = a[i];
idx = i;
}
else if(isMax == false && a[i] <= Min) {
Min = a[i];
idx = i;
}
}
}
if(x == -1) {
x = idx;
}
else if(y == -1) {
y = idx;
}
else if(z == -1) {
z = idx;
}
return a[idx];
}
int main() {
if (fopen("TICHMAX.INP", "r")) {
freopen("TICHMAX.INP", "r", stdin);
freopen("TICHMAX.OUT", "w", stdout);
}
int n;
cin >> n;
long long a[n];
int iMax1 = 0, iMin1 = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
if(a[i] > a[iMax1]) {
iMax1 = i;
}
if(a[i] < a[iMin1]) {
iMin1 = i;
}
}
long long Max1 = a[iMax1];
long long Min1 = a[iMin1];
int x = iMax1, y = -1, z = -1;
long long Max2 = FindMinOrMax(a, n, x, y, z, true);
long long Max3 = FindMinOrMax(a, n, x, y, z, true);
x = iMin1;
y = z = -1;
long long Min2 = FindMinOrMax(a, n, x, y, z, false);
cout << max(Max1 * Max2 * Max3, Min1 * Min2 * Max1);
return 0;
}import sys, os
def FindMinOrMax(a, n, xyz, isMax):
Max = -10**18
Min = 10**18
idx = -1
x, y, z = xyz
for i in range(n):
if i != x and i != y and i != z:
if isMax and a[i] >= Max:
Max = a[i]
idx = i
elif not isMax and a[i] <= Min:
Min = a[i]
idx = i
# gán chỉ số vào x, y, z theo thứ tự
if x == -1:
x = idx
elif y == -1:
y = idx
elif z == -1:
z = idx
return a[idx], (x, y, z)
# đọc / ghi file như trong C++
if os.path.exists("TICHMAX.INP"):
sys.stdin = open("TICHMAX.INP", "r")
sys.stdout = open("TICHMAX.OUT", "w")
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().split()))
iMax1 = 0
iMin1 = 0
for i in range(n):
if a[i] > a[iMax1]:
iMax1 = i
if a[i] < a[iMin1]:
iMin1 = i
Max1 = a[iMax1]
Min1 = a[iMin1]
# tìm 2 số lớn tiếp theo (Max2, Max3)
xyz = (iMax1, -1, -1)
Max2, xyz = FindMinOrMax(a, n, xyz, True)
Max3, xyz = FindMinOrMax(a, n, xyz, True)
# tìm số nhỏ thứ 2 (Min2)
xyz = (iMin1, -1, -1)
Min2, xyz = FindMinOrMax(a, n, xyz, False)
res = max(Max1 * Max2 * Max3, Min1 * Min2 * Max1)
print(res)Đánh giá độ phức tạp: thời gian $O(N)$ (5 lượt duyệt, mỗi lượt $N$ phần tử), không gian $O(N)$.
Cách 3Một vòng lặp, không cần mảng – O(N), bộ nhớ O(1)
Như cách làm ở trên tuy độ phức tạp tối ưu hơn cách làm sắp xếp ban đầu nhưng vẫn chưa phải là tối ưu nhất. Vẫn còn dài dòng phức tạp xử lý đến 5 vòng lặp. Cách tối ưu nhất là ta hoàn toàn có thể chỉ cần 1 vòng lặp duy nhất xét qua toàn bộ các phần tử của mảng là tìm ra được 3 số lớn nhất và 2 số nhỏ nhất. Đây cũng từng là 1 câu hỏi phỏng vấn tuyển dụng của FPT. Tư tưởng giải quyết như sau:
Ta tạo ra bộ 3 biến max1, max2, max3 tương ứng là 3 giá trị lớn nhất, nhì, ba. Tương tự 2 biến min1, min2 tương ứng là 2 giá trị nhỏ nhất, nhì.
3 biến max ban đầu sẽ khởi tạo giá trị là −30001 để đảm bảo mọi giá trị trong mảng lần đầu tiên so sánh với nó sẽ luôn lớn hơn nó, để từ đó cập nhật lại giá trị mới vào các biến này (các phần tử trong mảng theo như đề bài cho có miền giá trị từ −30000 đến 30000). Tương tự 2 biến min ban đầu sẽ khởi tạo giá trị là 30001 để đảm bảo mọi giá trị trong mảng lần đầu tiên so sánh với nó sẽ luôn nhỏ hơn nó.
Thì giờ đây chỉ cần 1 vòng lặp duyệt qua từng phần tử của mảng và ta luôn cập nhật đồng thời bộ 3 phần tử max cũng như bộ 2 phần tử min. Để làm được điều đó thì như sau:
- Gặp phần tử nào mà lớn hơn max1 (số lớn nhất) thì max1 phải trao lại giá trị hiện tại của nó cho max2, nhưng nếu max2 muốn nhận giá trị từ max1 thì trước đó max2 cũng phải trao lại giá trị hiện tại của nó cho max3 rồi thì max2 mới nhận được giá trị mới từ max1. Khi nào trao lại giá trị xong xuôi hết thì max1 mới nhận giá trị số đang so sánh. Ta luôn phải cập nhật đồng thời như thế để duy trì được bộ 3 biến này luôn là 3 giá trị lớn nhất.
- Nếu giá trị đang xét không lớn hơn max1 nhưng lại lớn hơn max2 thì max2 phải trao lại giá trị hiện tại cho max3 rồi max2 mới được nhận giá trị mới.
- Nếu giá trị đang xét không lớn hơn max1 hay max2 nhưng lại lớn hơn max3 thì lúc này max3 là thằng cuối trong bộ 3 rồi nên nó không cần trao giá trị lại cho thằng nào khác, chính nó nhận luôn giá trị hiện tại.
Quy trình ở trên làm tương tự với 2 biến min1, min2. Nếu gặp thằng nào nhỏ hơn min1 thì min1 gán giá trị hiện tại của nó cho min2 rồi min1 mới nhận giá trị mới. Nếu gặp thằng nào không nhỏ hơn min1 nhưng lại nhỏ hơn min2 thì min2 là thằng cuối trong bộ 2 rồi nên nó không cần trao giá trị lại cho thằng nào khác, chính nó nhận luôn giá trị hiện tại.
Cứ như thế ta chỉ cần duyệt hết 1 lần vòng lặp và luôn kiểm tra cập nhật liên tục 5 biến rồi sau cùng chỉ cần tìm max của max1 * max2 * max3 so với min1 * min2 * max1. Em nhập dãy rồi bấm Tiếp để xem các biến "trao giá trị" cho nhau như thế nào:
Dễ dàng nhận ra một chỗ tối ưu hơn nữa khi ta chẳng cần dùng mảng để lưu trữ danh sách các số đầu vào. Bởi vì với tư tưởng này mỗi giá trị đầu vào ta chỉ xét qua 1 lần duy nhất nên ta đâu cần lưu trữ vào mảng làm gì, ta tạo 1 biến x đọc giá trị từ input vào và xử lý so sánh thôi. Như thế này thì độ phức tạp không gian chỉ cần $O(1)$ chứ không cần $O(N)$ như các cách làm trước.
Mình cũng code thử theo hướng này cho anh em tham khảo để nhìn thấy rõ hơn những gì mình đã phân tích:
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
if (fopen("TICHMAX.INP", "r")) {
freopen("TICHMAX.INP", "r", stdin);
freopen("TICHMAX.OUT", "w", stdout);
}
int n;
cin >> n;
long long max1, max2, max3;
long long min1, min2;
max1 = max2 = max3 = -30001;
min1 = min2 = 30001;
while(n--) {
long long x;
cin >> x;
if(x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
}
else if(x > max2) {
max3 = max2;
max2 = x;
}
else if(x > max3) {
max3 = x;
}
if(x < min1) {
min2 = min1;
min1 = x;
}
else if(x < min2) {
min2 = x;
}
}
cout << max(max1 * max2 * max3, min1 * min2 * max1);
return 0;
}import sys, os
if os.path.exists("TICHMAX.INP"):
sys.stdin = open("TICHMAX.INP", "r")
sys.stdout = open("TICHMAX.OUT", "w")
data = list(map(int, sys.stdin.read().strip().split()))
n = data[0]
arr = data[1:]
max1 = max2 = max3 = -30001
min1 = min2 = 30001
for x in arr:
if x > max1:
max3 = max2
max2 = max1
max1 = x
elif x > max2:
max3 = max2
max2 = x
elif x > max3:
max3 = x
if x < min1:
min2 = min1
min1 = x
elif x < min2:
min2 = x
res = max(max1 * max2 * max3, min1 * min2 * max1)
print(res)Đánh giá độ phức tạp: thời gian $O(N)$, không gian $O(1)$.
Rồi xong, chỉ một bài này thôi nhưng mình giải theo 3 cách làm khác nhau với độ phức tạp tối ưu dần. Hi vọng anh em học được nhiều kiến thức.
fopen / os.path.exists để chạy được cả khi có file lẫn khi không có file. Tất cả 6 bản đã được kiểm tra với 300 bộ test ngẫu nhiên (có số âm, số 0, nhiều số trùng nhau, $N = 3$) so với code vét cạn thử mọi bộ 3 số: khớp 100%. Với $N = 10000$, các bản C++ chạy dưới 0.06 giây, bản Python khoảng 0.1 giây.
Nhận xét
Đăng nhận xét