Mua Hàng (HSG9 Hà Nội 2025 – Bài 5)
Đề bài
MUA HÀNG
An đi mua $M$ sản phẩm khác nhau, các sản phẩm được đánh số từ $1$ đến $M$. Ở chợ có $N$ quầy hàng xếp thành hàng ngang được đánh số từ $1$ đến $N$, từ trái sang phải. Quầy hàng thứ $i$ chỉ bán một loại sản phẩm duy nhất là $A_i$ $(1 \le A_i \le M)$ và với mỗi sản phẩm trong $M$ sản phẩm luôn tồn tại ít nhất một quầy hàng bán sản phẩm loại đó. Thời gian để An mua sản phẩm tại quầy hàng thứ $i$ là $T_i$ phút. Thời gian để di chuyển giữa hai quầy hàng liền kề là $1$ phút.
Yêu cầu: Tìm cách mua hàng sao cho:
- Mua đủ $M$ sản phẩm theo đúng thứ tự $1, 2, 3, \ldots, M$. Có thể bắt đầu từ một quầy hàng bất kì bán sản phẩm $1$;
- Thời gian tính từ lúc bắt đầu mua sản phẩm $1$ đến khi mua xong sản phẩm $M$ là nhỏ nhất.
Dữ liệu vào từ file văn bản MUAHANG.INP:
- Dòng đầu tiên gồm hai số nguyên dương $N, M$ $(1 \le M \le N \le 10^5)$;
- Dòng thứ hai gồm $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le M;\ 1 \le i \le N)$. Dữ liệu đảm bảo các số từ $1$ đến $M$ xuất hiện ít nhất một lần;
- Dòng thứ ba gồm $N$ số nguyên dương $T_1, T_2, \ldots, T_N$ $(1 \le T_i \le 10^9;\ 1 \le i \le N)$.
Kết quả ghi ra file văn bản MUAHANG.OUT: Một số nguyên duy nhất là số phút nhỏ nhất để An mua $M$ sản phẩm theo yêu cầu đề bài.
Ràng buộc:
- Có $10\%$ số test ứng với $10\%$ số điểm của bài thoả mãn: $M = 1$;
- $30\%$ số test khác ứng với $30\%$ số điểm của bài thoả mãn: $M = N$;
- $30\%$ số test khác ứng với $30\%$ số điểm của bài thoả mãn: $N \le 2000$;
- $30\%$ số test còn lại ứng với $30\%$ số điểm không có ràng buộc gì thêm.
Lưu ý: đề thi gốc đọc/ghi file MUAHANG.INP / MUAHANG.OUT; trên CLUE OJ thì đọc từ bàn phím và in ra màn hình (code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng).
5 2
1 2 1 1 2
5 10 6 8 311Giải thích (theo đề): Cách mua sao cho tổng số phút nhỏ nhất là:
- Mua sản phẩm $1$ ở quầy hàng thứ $3$ mất $6$ phút;
- Di chuyển sang quầy hàng thứ $5$ mất $2$ phút;
- Mua sản phẩm $2$ ở quầy hàng thứ $5$ mất $3$ phút;
Tổng số phút là: $6 + 2 + 3 = 11$.
Lời mở đầu
Đây là bài cuối (bài 5) trong đề thi học sinh giỏi Tin học lớp 9 thành phố Hà Nội năm 2025. Bài này có 4 subtask, đi từ rất dễ (chỉ cần tìm min) cho tới một bài quy hoạch động phải tối ưu thêm bằng hai con trỏ mới ăn trọn điểm. Đây là một bài rất hay để các bạn lớp 9 làm quen với tư tưởng quy hoạch động, nên mình viết kỹ từng subtask một. Hy vọng mang đến được giá trị cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây 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 OJMình giải thích thêm ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $5$ quầy, cần mua sản phẩm $1$ rồi tới sản phẩm $2$. Sản phẩm $1$ bán ở quầy $1, 3, 4$; sản phẩm $2$ bán ở quầy $2, 5$. Thời gian = thời gian mua ở các quầy được chọn + số bước đi giữa các quầy. Ta thử hết các cách:
| Mua SP 1 ở quầy | Mua SP 2 ở quầy | Thời gian |
|---|---|---|
| 1 ($T = 5$) | 2 ($T = 10$) | $5 + 1 + 10 = 16$ |
| 1 ($T = 5$) | 5 ($T = 3$) | $5 + 4 + 3 = 12$ |
| 3 ($T = 6$) | 2 ($T = 10$) | $6 + 1 + 10 = 17$ |
| 3 ($T = 6$) | 5 ($T = 3$) | $6 + 2 + 3 = 11$ |
| 4 ($T = 8$) | 2 ($T = 10$) | $8 + 2 + 10 = 20$ |
| 4 ($T = 8$) | 5 ($T = 3$) | $8 + 1 + 3 = 12$ |
Nhỏ nhất là $11$. Để ý An được phép đi qua các quầy khác (đi ngang qua quầy 4 khi đi từ quầy 3 sang quầy 5) mà không mua gì, và quầy bắt đầu là quầy nào cũng được, không mất thời gian đi tới quầy đầu tiên.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1M = 1: chọn quầy nhanh nhất – O(N)
Chỉ có một loại hàng duy nhất, do đó ta không cần phải di chuyển giữa hai quầy hàng. Ta chỉ việc chọn quầy có thời gian bán ít nhất. Kết quả bài toán chính là giá trị nhỏ nhất của dãy $T$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[100005], t[100005];
signed main(){
if(fopen("muahang.inp", "r")){
freopen("muahang.inp", "r", stdin);
freopen("muahang.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
int res = 1e18;
for (int i = 1; i <= n; i++){
cin >> t[i];
res = min(res, t[i]);
}
cout << res;
}import sys, os
if os.path.exists('muahang.inp'):
sys.stdin = open('muahang.inp')
sys.stdout = open('muahang.out', 'w')
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
t = [0] + [int(v) for v in data[2 + n:2 + 2 * n]]
# Subtask 1 (M = 1): chọn quầy mua nhanh nhất
print(min(t[1:]))
sys.stdout.flush()Trong khung chạy tay mình có để cả nút Test đề – test này có $M = 2$, không thuộc subtask 1 nên code in ra $3$ (sai), các bạn thấy rõ vì sao code này chỉ dùng được khi $M = 1$ nha:
long long) cho cả những bài tổng có thể rất lớn – như ở các subtask sau, tổng thời gian có thể lên tới $10^5 \cdot 10^9 = 10^{14}$.Subtask 2M = N: chỉ có đúng một cách đi – O(N)
Vì $M = N$ và mỗi loại hàng phải có ít nhất một quầy bán, mà có $N$ quầy cho $N$ loại hàng, nên mỗi loại hàng chỉ có đúng một quầy bán. Do đó kế hoạch mua hàng của chúng ta là duy nhất: mua sản phẩm $1$ ở quầy duy nhất bán nó, rồi đi tới quầy duy nhất bán sản phẩm $2$…
Khi này, ta lưu $ps[v]$ là vị trí của quầy bán mặt hàng $v$. Duyệt $i$ từ $1$ đến $M$, ta lưu vị trí $lst$ trước đó đã đứng (với mặt hàng $1$ thì $lst = ps[1]$ luôn, vì quầy bắt đầu không mất thời gian di chuyển), và cộng vào biến kết quả một lượng là $T[ps[i]]$ (thời gian mua mặt hàng $i$) cộng với khoảng cách $|ps[i] - lst|$ giữa quầy cũ và quầy hiện tại.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[100005], t[100005], ps[100005];
signed main(){
if(fopen("muahang.inp", "r")){
freopen("muahang.inp", "r", stdin);
freopen("muahang.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> a[i];
ps[a[i]] = i;
}
int res = 0;
for (int i = 1; i <= n; i++){
cin >> t[i];
}
int lst = ps[1];
for (int i = 1; i <= m; i++){
res += t[ps[i]];
res += abs(ps[i] - lst);
lst = ps[i];
}
cout << res;
}import sys, os
if os.path.exists('muahang.inp'):
sys.stdin = open('muahang.inp')
sys.stdout = open('muahang.out', 'w')
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
t = [0] + [int(v) for v in data[2 + n:2 + 2 * n]]
# Subtask 2 (M = N): mỗi sản phẩm chỉ có đúng một quầy bán
ps = [0] * (m + 1)
for i in range(1, n + 1):
ps[a[i]] = i
res = 0
lst = ps[1]
for i in range(1, m + 1):
res += t[ps[i]]
res += abs(ps[i] - lst)
lst = ps[i]
print(res)
sys.stdout.flush()ps[a[i]] = i chỉ nhớ quầy cuối cùng, và code sẽ đi theo một đường cố định chưa chắc tối ưu. Ở test đề, code này in ra $12$ thay vì $11$ (nút Test đề ở khung trên). Khi mỗi sản phẩm có nhiều lựa chọn, ta cần quy hoạch động.Subtask 3Quy hoạch động – O(N²)
Đến đây chúng ta sẽ làm quen với tư tưởng quy hoạch động. Gọi:
Vì mỗi quầy chỉ bán một loại sản phẩm nên chỉ cần một chỉ số $j$ là đủ biết "đang mua đến món nào, ở quầy nào". Ta cũng nhận thấy rằng ta sẽ ưu tiên tính các $dp[j]$ có $A_j$ nhỏ trước, vì ta cần mua hàng theo thứ tự từ $1$ đến $M$. Để tiện, gọi $p[i]$ là danh sách các quầy bán sản phẩm $i$ (theo thứ tự tăng dần). Duyệt $i$ từ $1$ đến $M$ và giả sử đang mua đến món đồ thứ $i$:
- Nếu $i = 1$: đối với những $j$ mà $A_j = 1$, ta chỉ mất thời gian mua hàng chứ không mất chi phí di chuyển (vì đây được coi là điểm bắt đầu). Do đó $dp[j] = T_j$.
- Nếu $i \gt 1$: đối với những $j$ mà $A_j = i$, ta tính $dp[j]$ từ các $dp[k]$ sao cho $A_k = i - 1$ – nghĩa là ta đang xem xét những quầy $k$ có thể là nơi mua món ngay trước món thứ $i$. Từ quầy $k$, ta mất chi phí di chuyển $|j - k|$ sang quầy $j$ và mất thêm $T_j$ thời gian mua đồ.
Ở ví dụ: $p[1] = \{1, 3, 4\}$ nên $dp[1] = 5$, $dp[3] = 6$, $dp[4] = 8$. Với $p[2] = \{2, 5\}$: $dp[2] = 10 + \min(5 + 1, 6 + 1, 8 + 2) = 16$; $dp[5] = 3 + \min(5 + 4, 6 + 2, 8 + 1) = 11$. Đáp án $\min(16, 11) = 11$ ✔.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[100005], t[100005], dp[100005];
vector<int> p[100005];
signed main(){
if(fopen("muahang.inp", "r")){
freopen("muahang.inp", "r", stdin);
freopen("muahang.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++){
dp[i] = 1e18;
p[a[i]].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> t[i];
int ans = 1e18;
for (int i = 1; i <= m; i++){
if (i == 1){
for (auto j : p[i]){
dp[j] = t[j];
if (i == m) ans = min(ans, dp[j]);
}
continue;
}
for (auto j : p[i]){
for (auto k : p[i - 1]){
dp[j] = min(dp[j], t[j] + dp[k] + abs(j - k));
if (i == m) ans = min(ans, dp[j]);
}
}
}
cout << ans << endl;
}import sys, os
if os.path.exists('muahang.inp'):
sys.stdin = open('muahang.inp')
sys.stdout = open('muahang.out', 'w')
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
t = [0] + [int(v) for v in data[2 + n:2 + 2 * n]]
INF = 10 ** 18
p = [[] for _ in range(m + 1)] # p[v] = các quầy bán sản phẩm v (tăng dần)
for i in range(1, n + 1):
p[a[i]].append(i)
dp = [INF] * (n + 1)
for j in p[1]:
dp[j] = t[j]
for i in range(2, m + 1):
for j in p[i]:
for k in p[i - 1]:
dp[j] = min(dp[j], t[j] + dp[k] + abs(j - k))
print(min(dp[j] for j in p[m]))
sys.stdout.flush()Trong code, mình cập nhật ans ngay trong vòng lặp khi $i = M$, và dùng vector<int> p[100005] – mảng các vector, p[v] chứa các quầy bán sản phẩm $v$. Vì ta duyệt $i$ từ $1$ đến $N$ và push_back nên mỗi p[v] tự động tăng dần. Lưu ý trường hợp $M = 1$ được xử lý luôn trong nhánh if (i == 1).
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho các mảng và các vector $p$ (tổng kích thước đúng bằng $N$).
- Thời gian: với mỗi $i$ ta duyệt $|p[i]| \cdot |p[i - 1]|$ cặp $(j, k)$. Tệ nhất (ví dụ $M = 2$, mỗi sản phẩm có khoảng $N/2$ quầy) là khoảng $N^2/4$ cặp: $O(N^2)$. Với $N \le 2000$ thì chỉ khoảng $10^6$ phép tính.
Subtask 4QHĐ + hai con trỏ – O(N)
Vẫn giữ nguyên tư tưởng ở subtask 3, nhưng ta sẽ cố gắng tối ưu hơn một chút. Với $i \gt 1$, đối với những $j$ mà $A_j = i$ ($j \in p[i]$), $T_j$ đã được cố định sẵn nên ta cần tìm quán $k$ với $A_k = i - 1$ sao cho $dp[k] + |j - k|$ là nhỏ nhất có thể. Cái khó là dấu giá trị tuyệt đối. Ta tách nó ra làm hai trường hợp:
Giờ làm sao lấy nhanh "min của các $k \ge j$"? Ta có thể duyệt lần lượt các $j$ từ lớn nhất đến nhỏ nhất. Khi $j$ giảm dần thì tập các $k \ge j$ chỉ có thêm vào chứ không bao giờ bớt đi! Vậy ta duy trì một con trỏ $r$ trên $p[i - 1]$ (cũng đi từ cuối về đầu) và biến $mn$: mỗi khi $p[i-1][r] \ge j$ thì "nạp" quầy đó vào, cập nhật $mn = \min(mn, dp[k] + k)$ rồi lùi $r$. Như vậy là dễ dàng cập nhật được $\min$ nhỏ nhất.
Trường hợp $k \le j$ thì tương tự, ta cũng duy trì con trỏ nhưng chỉ khác là duyệt $j$ từ nhỏ nhất lên lớn nhất, con trỏ $r$ chạy từ đầu $p[i-1]$, và $mn = \min(dp[k] - k)$. Mỗi quầy được con trỏ đi qua đúng một lần ở mỗi lượt, nên tổng chi phí cho sản phẩm $i$ chỉ là $O(|p[i]| + |p[i - 1]|)$.
Các bạn xem khung minh hoạ: dòng "SP" là sản phẩm của quầy, ô vàng nhạt là các quầy bán sản phẩm $i - 1$, ô xanh nhạt là các quầy bán sản phẩm $i$. Viền cam là quầy $j$ đang tính, viền xanh lá là các quầy $k$ đã được "nạp" vào $mn$:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[100005], t[100005], dp[100005];
vector<int> p[100005];
signed main(){
if(fopen("muahang.inp", "r")){
freopen("muahang.inp", "r", stdin);
freopen("muahang.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++){
dp[i] = 1e18;
p[a[i]].push_back(i);
}
for (int i = 1; i <= n; i++) cin >> t[i];
int ans = 1e18;
for (int i = 1; i <= m; i++){
if (i == 1){
for (auto j : p[i]){
dp[j] = t[j];
if (i == m) ans = min(ans, dp[j]);
}
continue;
}
int r = p[i - 1].size() - 1;
int mn = 1e18;
reverse(p[i].begin(), p[i].end());
for (auto j : p[i]){
while (r >= 0 && p[i - 1][r] >= j){
mn = min(mn, dp[p[i - 1][r]] + p[i - 1][r]);
r--;
}
dp[j] = min(dp[j], t[j] + mn - j);
}
r = 0;
mn = 1e18;
reverse(p[i].begin(), p[i].end());
for (auto j : p[i]){
while (r < p[i - 1].size() && p[i - 1][r] <= j){
mn = min(mn, dp[p[i - 1][r]] - p[i - 1][r]);
r++;
}
dp[j] = min(dp[j], t[j] + mn + j);
if (i == m) ans = min(ans, dp[j]);
}
}
cout << ans << endl;
}import sys, os
if os.path.exists('muahang.inp'):
sys.stdin = open('muahang.inp')
sys.stdout = open('muahang.out', 'w')
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]
t = [0] + [int(v) for v in data[2 + n:2 + 2 * n]]
INF = 10 ** 18
p = [[] for _ in range(m + 1)] # p[v] = các quầy bán sản phẩm v (tăng dần)
for i in range(1, n + 1):
p[a[i]].append(i)
dp = [INF] * (n + 1)
for j in p[1]:
dp[j] = t[j]
for i in range(2, m + 1):
prv, cur = p[i - 1], p[i]
# lượt 1: các quầy k >= j (đi từ bên phải sang), dp[j] = t[j] + min(dp[k] + k) - j
r = len(prv) - 1
mn = INF
for j in reversed(cur):
while r >= 0 and prv[r] >= j:
mn = min(mn, dp[prv[r]] + prv[r])
r -= 1
dp[j] = min(dp[j], t[j] + mn - j)
# lượt 2: các quầy k <= j (đi từ bên trái sang), dp[j] = t[j] + min(dp[k] - k) + j
r = 0
mn = INF
for j in cur:
while r < len(prv) and prv[r] <= j:
mn = min(mn, dp[prv[r]] - prv[r])
r += 1
dp[j] = min(dp[j], t[j] + mn + j)
print(min(dp[j] for j in p[m]))
sys.stdout.flush()Giải thích 1 số chỗ trong code ở trên:
reverse(p[i].begin(), p[i].end())lần thứ nhất để duyệt các $j$ từ lớn đến nhỏ cho lượt 1, lần thứ hai để đảo lại về tăng dần cho lượt 2 (và đểp[i]tăng dần khi nó đóng vai tròp[i - 1]ở sản phẩm tiếp theo).- Ở lượt 1, nếu chưa có quầy $k \ge j$ nào thì $mn = 10^{18}$, $dp[j]$ tạm thời thành một số cỡ $10^{18}$ (vẫn vừa
long long, không tràn) và sẽ được lượt 2 sửa lại. Vì mỗi sản phẩm luôn có ít nhất một quầy bán nên mỗi $j$ chắc chắn có $k$ ở ít nhất một phía. - Không thể có $k = j$ vì mỗi quầy chỉ bán một loại sản phẩm, nên dấu $\ge$, $\le$ ở hai lượt không bị tính trùng gây sai.
r < p[i - 1].size()so sánhlong longvới số không dấu (size_t) – trình biên dịch có thể cảnh báo nhưng ở đây $r \ge 0$ nên vẫn đúng.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: với sản phẩm $i$, hai lượt duyệt và hai lần
reversetốn $O(|p[i]| + |p[i - 1]|)$. Cộng lại cho mọi $i$ thì mỗi quầy được tính tối đa vài lần, tổng là $O(N + M) = O(N)$.
- 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