Xếp Hàng Mua Vé (NKTICK)
Đề bài
Có $N$ người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ $1$ đến $N$ theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết $t_i$ là thời gian cần thiết để người $i$ mua xong vé cho mình. Nếu người $i + 1$ rời khỏi hàng và nhờ người $i$ mua hộ vé thì thời gian để người thứ $i$ mua được vé cho cả hai người là $r_i$.
Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.
Input:
- Dòng đầu tiên chứa số $N$ $(1 \le N \le 60000)$.
- Dòng thứ hai ghi $N$ số nguyên dương $t_1, t_2, \dots, t_N$ $(1 \le t_i \le 30000)$.
- Dòng thứ ba ghi $N - 1$ số nguyên dương $r_1, r_2, \dots, r_{N-1}$ $(1 \le r_i \le 30000)$.
Output: In ra tổng thời gian phục vụ nhỏ nhất.
5
2 5 7 8 4
4 9 10 1018Lờ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 😇. Đây là một bài quy hoạch động "nhập môn" rất kinh điển, rất hợp để các bạn luyện cách suy nghĩ theo 4 bước của quy hoạch động.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Hàng có $5$ người với $t = (2, 5, 7, 8, 4)$ và $r = (4, 9, 10, 10)$. Cách tốt nhất là:
- Người 2 rời hàng, nhờ người 1 mua hộ: người 1 mua 2 vé mất $r_1 = 4$ (thay vì $t_1 + t_2 = 2 + 5 = 7$).
- Người 4 rời hàng, nhờ người 3 mua hộ: người 3 mua 2 vé mất $r_3 = 10$ (thay vì $t_3 + t_4 = 7 + 8 = 15$).
- Người 5 tự mua vé cho mình: $t_5 = 4$.
Tổng thời gian: $4 + 10 + 4 = 18$, đúng như output. Các bạn để ý: người $5$ mà nhờ người $4$ mua hộ thì không được vì người $4$ đã rời hàng rồi; còn nếu cho người 4 tự mua và người 5 nhờ người 4 thì tốn $r_4 = 10$, tệ hơn. Mỗi lần bán tối đa 2 vé, nên hàng người thực chất bị chia thành các khúc liên tiếp dài 1 hoặc 2 người – đó chính là chìa khoá của bài.
Đề có chữ "xác định những người nào cần rời hàng" nhưng output chỉ yêu cầu in tổng thời gian nhỏ nhất thôi nhé. (Trong khung minh hoạ bên dưới mình có truy vết luôn để các bạn thấy ai rời hàng.)
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 1Quy hoạch động 4 bước – O(N)
Bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé các bạn. Cho bạn nào đã biết cơ bản về quy hoạch động rồi thì 4 bước giải một bài quy hoạch động như sau:
Bước 1 – Xác định bài toán con: gọi $F[i]$ là thời gian ít nhất để bán vé cho $i$ người tính từ đầu hàng (vị trí $1$) đến vị trí $i$.
Bước 2 – Bài toán cơ sở:
- $F[0] = 0$: hàng không có người nào thì đâu mất thời gian gì để bán.
- $F[1] = T[1]$: hàng chỉ có 1 người thì thời gian bán vé cho người đó chính là $T[1]$.
Bước 3 – Đáp án: quá rõ ràng, đó chính là $F[N]$ vì đề đang hỏi thời gian ít nhất để bán hết vé cho $N$ người.
Bước 4 – Công thức truy hồi: ta đã gọi $F[i]$ là thời gian ít nhất cho $i$ người, thì $F[i-1]$ là thời gian ít nhất cho $i-1$ người, $F[i-2]$ là thời gian ít nhất cho $i-2$ người. Nguyên tắc của quy hoạch động (cũng như đệ quy) là ta giả định những kết quả $F[i-1]$, $F[i-2]$ đã được tính chính xác rồi, từ đó suy ra $F[i]$. Khi xét đến người thứ $i$ chỉ có 2 tình huống:
Minh hoạ tính mảng F và truy vết
Em nhập $t$ và $r$ rồi bấm Tiếp để xem từng ô $F[i]$ được chọn từ lựa chọn nào. Sau khi tính xong, mình truy ngược từ $F[N]$ về để chỉ ra luôn những ai rời hà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;
cin >> n;
int t[n + 1];
for(int i = 1; i <= n; ++i){
cin >> t[i];
}
int r[n];
for(int i = 1; i < n; ++i){
cin >> r[i];
}
int f[n + 1];
f[0] = 0;
f[1] = t[1];
for(int i = 2; i <= n; ++i){
f[i] = min(f[i - 1] + t[i], f[i - 2] + r[i - 1]);
}
cout << f[n];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
t = [0] + [int(x) for x in data[1:n + 1]]
r = [0] + [int(x) for x in data[n + 1:2 * n]]
f = [0] * (n + 1)
f[0] = 0
f[1] = t[1]
for i in range(2, n + 1):
f[i] = min(f[i - 1] + t[i], f[i - 2] + r[i - 1])
print(f[n])Giải thích một số chỗ trong code:
- 2 dòng đầu hàm
main(ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code 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: bài nào cần nhập xuất nhiều thì nên thêm 2 dòng này vào đầu cho chương trình chạy nhanh hơn. - Vị trí trong bài tính từ 1, nên để thống nhất, tránh rắc rối, mình khai báo mảng
t,fcó $n + 1$ phần tử (chỉ số $0..n$), bỏ qua chỉ số 0 củat. Còn mảngrchỉ cần $n$ phần tử vìrtối đa chỉ tới $n - 1$, dùng chỉ số $1..n-1$.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(3 \cdot N)$ là tổng bộ nhớ của 3 mảng $T$, $R$, $F$.
- Thời gian: $O(N)$ đọc mảng $T$ + $O(N)$ đọc mảng $R$ + $O(N)$ tính mảng $F$, tổng là $O(3 \cdot N)$.
Theo quy tắc Big-O thì nhân với hằng số ta bỏ qua được, nên về lý thuyết cả không gian lẫn thời gian đều là $O(N)$. Với trường hợp xấu nhất $N = 60000$ thì $3 \cdot N = 180000$ lần lặp, trong khi giới hạn 1 giây cho phép cỡ $(3 \div 5) \cdot 10^7$, cao lắm là $10^8$ phép tính, tức ít hơn ngưỡng cả vài trăm lần, chắc chắn không thể nào TLE được.
int (tối đa khoảng $2.147 \cdot 10^9$).Nếu đi thi bị giới hạn thời gian mà gặp bài này thì là mình, mình sẽ code đúng như trên là đủ, vì nó thể hiện tư tưởng rất trực quan, dễ cài đặt, còn thời gian làm bài khác. Tuy nhiên nếu thoải mái thời gian thì ta thử nghĩ xem có tối ưu thêm được không, cả về không gian lẫn thời gian?
Cách 2Bỏ mảng R, đọc tới đâu dùng tới đó – O(N)
Các bạn để ý sẽ thấy: trước bước tính mảng $F$ ta có một vòng lặp đọc mảng $R$ từ $R[1]$ đến $R[N-1]$. Rồi khi tính $F$ với $i$ chạy từ $2$ đến $N$ thì mảng $R$ chỉ được dùng duy nhất ở $R[i-1]$, tức là gọi lần lượt $R[1], R[2], \dots, R[N-1]$ – đúng y thứ tự đọc vào.
r: ở bước $i$ đọc vào giá trị $R[i-1]$ rồi dùng luôn. Như vậy ta đỡ được $O(N)$ bộ nhớ và một vòng lặp $O(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;
int t[n + 1];
for(int i = 1; i <= n; ++i){
cin >> t[i];
}
int r;
int f[n + 1];
f[0] = 0;
f[1] = t[1];
for(int i = 2; i <= n; ++i){
cin >> r;
f[i] = min(f[i - 1] + t[i], f[i - 2] + r);
}
cout << f[n];
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
t = [0] + [int(x) for x in data[1:n + 1]]
pos = n + 1 # vị trí của r[1] trong dữ liệu
f = [0] * (n + 1)
f[0] = 0
f[1] = t[1]
for i in range(2, n + 1):
r = int(data[pos])
pos += 1
f[i] = min(f[i - 1] + t[i], f[i - 2] + r)
print(f[n])Về Big-O thì vẫn là $O(N)$, nhưng thực tế ta bớt được hẳn một mảng và một vòng lặp so với cách 1.
Cách 3Bỏ luôn mảng F, chỉ còn 3 biến – O(N)
Thậm chí còn một chỗ nữa có thể tối ưu, nhưng chỉ là tối ưu bộ nhớ thôi, còn thời gian không thay đổi (thậm chí có phần tệ hơn nên các bạn cân nhắc khi dùng). Đó là $F[i]$ chỉ gọi lại $F[i-1]$ và $F[i-2]$, tức là chỉ cần 2 giá trị ngay trước nó.
f0, f1, fn: ban đầu f0 = F[0] = 0, f1 = F[1] = T[1]. Ở mỗi bước tính fn = min(f1 + t[i], f0 + r), rồi "dịch cửa sổ": f0 = f1; f1 = fn;. Nhờ cập nhật liên tục như vậy, khi sang vòng sau thì f0, f1 luôn là 2 giá trị liền trước của ô đang tính.Về thời gian thì có thể thấy còn tệ hơn chút xíu: mỗi bước lặp ta phải làm thêm 2 phép gán, $N = 60000$ thì thêm $120000$ phép gán, trong khi dùng mảng $F$ thì cứ gọi $F[i-1]$, $F[i-2]$ là có vì đã lưu lại rồi. Đa phần các bài giải thuật quan trọng yếu tố thời gian hơn, còn bộ nhớ thường dư dả, nên mình thấy tối ưu này không thật sự cần. Mình cứ nói ra để nếu gặp tình huống đặc biệt phải tối ưu bộ nhớ (ví dụ ai đó thử thách các bạn chẳng hạn hehe 😁) thì các bạn vẫn biết chỗ mà tối ưu.
fn. Nhưng nếu $N = 1$ thì vòng lặp không chạy lần nào, fn chưa từng được gán nên in ra giá trị rác! Sửa rất đơn giản: in f1 thay vì fn – sau mỗi vòng lặp f1 = fn nên với $N \ge 2$ kết quả y hệt, còn $N = 1$ thì f1 = t[1] đúng luôn. Code bên dưới mình đã sửa sẵn. Các bạn bấm nút N = 1 trong khung chạy tay để thấy nhé.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, r, f0, f1, fn;
cin >> n;
int t[n + 1];
for(int i = 1; i <= n; ++i){
cin >> t[i];
}
f0 = 0;
f1 = t[1];
for(int i = 2; i <= n; ++i){
cin >> r;
fn = min(f1 + t[i], f0 + r);
f0 = f1;
f1 = fn;
}
cout << f1;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
t = [0] + [int(x) for x in data[1:n + 1]]
pos = n + 1 # vị trí của r[1] trong dữ liệu
f0 = 0
f1 = t[1]
for i in range(2, n + 1):
r = int(data[pos])
pos += 1
fn = min(f1 + t[i], f0 + r)
f0 = f1
f1 = fn
print(f1)cin ta vẫn phải lưu mảng $T$. Với $N = 60000$ thì mảng này chỉ tốn khoảng 240 KB, chẳng đáng lo.- 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