Mua Sắm (HSG12 Hà Nội 2025 – Bài 2)
Đề bài
Bài II. Mua sắm (5,0 điểm)
Một cửa hàng trên sàn thương mại điện tử có $N$ sản phẩm khác nhau được niêm yết với giá tiền lần lượt là $A_1, A_2, \ldots, A_N$. Việt muốn mua hai sản phẩm, mỗi sản phẩm mua tối đa một lần, sao cho tổng số tiền phải trả nằm trong khoảng từ $L$ đến $R$.
Yêu cầu: Em hãy lập trình đưa ra số tiền nhỏ nhất mà Việt phải trả khi mua hai sản phẩm khác nhau mà tổng số tiền phải trả nằm trong đoạn $[L, R]$.
Dữ liệu vào từ file văn bản MUASAM.INP:
- Dòng đầu tiên gồm ba số nguyên dương $N, L, R$ $(N \le 10^6;\ 1 \le L \le R \le 10^9)$;
- Dòng thứ hai gồm $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ $(A_i \le 10^9;\ 1 \le i \le N)$.
Kết quả ghi ra file văn bản MUASAM.OUT: Một số nguyên duy nhất là kết quả của bài toán.
Dữ liệu đảm bảo luôn tồn tại ít nhất một cách mua thỏa mãn.
Ràng buộc:
- Có $80\%$ số test ứng với $80\%$ số điểm có $N \le 10^3$;
- $20\%$ số test còn lại ứng với $20\%$ số điểm không có ràng buộc gì thêm.
Lưu ý: trên hệ thống chấm online CLUE OJ thì đọc dữ liệu từ bàn phím và in kết quả ra màn hình (giới hạn trên CLUE OJ: 1 giây, 1 GB).
5 5 9
8 1 2 2 56Giải thích (trong đề): Mua hai sản phẩm $2$ và $5$ với tổng số tiền phải trả là $6$.
Lời mở đầu
Đây là bài 2 trong đề thi học sinh giỏi Tin học lớp 12 thành phố Hà Nội năm 2025. Bài này là một ví dụ rất đẹp cho lộ trình mà mình hay dạy: vét cạn để lấy điểm subtask trước, rồi sắp xếp + hai con trỏ để lấy trọn điểm. Mình viết lờ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 😇.
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 OJTóm tắt đề: chọn hai sản phẩm khác nhau (hai vị trí khác nhau, giá có thể trùng nhau) sao cho tổng giá nằm trong $[L, R]$, và trong các cách đó lấy tổng nhỏ nhất. Mình liệt kê hết các cặp của ví dụ ($L = 5$, $R = 9$, giá $8, 1, 2, 2, 5$) để bạn nào chưa hiểu đề sẽ hiểu rõ:
| Cặp giá | 8+1 | 8+2 | 8+2 | 8+5 | 1+2 | 1+2 | 1+5 | 2+2 | 2+5 | 2+5 |
|---|---|---|---|---|---|---|---|---|---|---|
| Tổng | 9 | 10 | 10 | 13 | 3 | 3 | 6 | 4 | 7 | 7 |
Các tổng nằm trong $[5, 9]$ (ô xanh) là $9, 6, 7, 7$; nhỏ nhất là $6$ (mua sản phẩm giá $1$ và giá $5$). Để ý tổng $3$, $4$ tuy nhỏ hơn nhưng lại nhỏ hơn $L$ nên không được tính.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Duyệt hết tất cả các cặp – O(N²)
Duy trì một biến $ans$ là kết quả của bài toán, ban đầu gán thật lớn ($2 \cdot 10^9$). Duyệt hết tất cả cặp chỉ số $(i, j)$ với $i \ne j$ và kiểm tra xem $a_i + a_j \ge L$ và $a_i + a_j \le R$ hay không. Nếu thoả mãn điều kiện thì mới cập nhật $ans = \min(ans, a_i + a_j)$ để tìm ra kết quả tối thiểu.
ans = min(ans, a[i] + a[j]). Đề đảm bảo luôn có cách mua nên cuối cùng $ans$ chắc chắn đã được cập 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 n, l, r, a[1000005];
namespace sub1{
int solve(){
int ans = 2e9;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= n; j ++){
if (i != j){
if (a[i] + a[j] >= l && a[i] + a[j] <= r) ans = min(ans, a[i] + a[j]);
}
}
}
return ans;
}
};
int main(){
if(fopen("MUASAM.inp", "r")){
freopen("MUASAM.inp", "r", stdin);
freopen("MUASAM.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l >> r;
for (int i = 1; i <= n; i ++) cin >> a[i];
cout << sub1::solve() << endl;
}import sys, os
def solve(n, l, r, a):
ans = 2 * 10**9
for i in range(1, n + 1):
for j in range(1, n + 1):
if i != j:
if a[i] + a[j] >= l and a[i] + a[j] <= r:
ans = min(ans, a[i] + a[j])
return ans
if os.path.exists("MUASAM.inp"):
sys.stdin = open("MUASAM.inp", "r")
sys.stdout = open("MUASAM.out", "w")
data = sys.stdin.buffer.read().split()
n, l, r = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
print(solve(n, l, r, a))Các bạn bấm Tiếp để chạy tay từng dòng; phần "Dữ liệu" vẽ mảng $a$ với hai con trỏ $i$, $j$ (ô xanh là cặp vừa thỏa mãn):
Giải thích 1 số chỗ trong code ở trên:
namespace sub1 { ... }: mình hay gói lời giải mỗi subtask vào mộtnamespaceriêng, trongmainmuốn dùng cách nào thì gọisub1::solve()haysub2::solve(). Trong phòng thi, cách này giúp các bạn giữ được code của subtask nhỏ (chắc chắn đúng) để vừa so sánh, vừa có thể "chia trường hợp" theo $N$.int ans = 2e9;: $2 \cdot 10^9$ vẫn nằm trong giới hạn củaint(tối đa $2^{31} - 1 \approx 2{,}147 \cdot 10^9$). Tổng hai giá $a_i + a_j \le 2 \cdot 10^9$ cũng vừa đủ chứa trongint, nên code không bị tràn số – nhưng sát giới hạn lắm đó nha, đề mà cho $A_i$ lớn hơn chút là phải dùnglong long.- Code duyệt cả $(i, j)$ lẫn $(j, i)$ – mỗi cặp bị xét 2 lần, không sai (chỉ chậm gấp đôi). Bạn nào muốn thì cho $j$ chạy từ $i + 1$ là gọn hơn.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho mảng $a$.
- Thời gian: hai vòng lặp lồng nhau, mỗi vòng $N$ lần nên là $O(N^2)$. Với $N \le 10^3$ là khoảng $10^6$ phép tính – chạy tức thì, ăn chắc $80\%$ số điểm.
Subtask 2Sắp xếp + hai con trỏ – O(N log N)
Nhận xét là việc chúng ta sắp xếp lại mảng $a$ theo thứ tự không giảm thì vẫn không ảnh hưởng đến kết quả của đề bài: đề chỉ hỏi tổng tiền của hai sản phẩm, chứ không quan tâm hai sản phẩm đứng ở vị trí nào. Sau khi sắp xếp, ví dụ thành $a = [1, 2, 2, 5, 8]$.
Giờ cố định sản phẩm rẻ hơn là $a_i$, ta đi tìm sản phẩm thứ hai $a_j$ với $j \gt i$. Vì mảng đã tăng dần nên tổng $a_i + a_j$ cũng tăng dần theo $j$. Muốn tổng nhỏ nhất mà vẫn $\ge L$, ta chọn $j$ là chỉ số nhỏ nhất ($j \gt i$) thỏa $a_i + a_j \ge L$. Nếu tổng đó còn $\le R$ thì nó là một ứng viên cho kết quả; nếu nó đã $\gt R$ thì mọi $j$ lớn hơn càng $\gt R$, sản phẩm $i$ không ghép được với ai.
Trong code của mình, chỉ số $j$ đó được giữ bằng biến $ps$ theo kiểu: $ps + 1$ chính là $j$ cần tìm. Duyệt $i$ từ $1$ đến $n$ và duy trì biến $ps$ sao cho $a_i + a_{ps+1} \ge L$ và $ps + 1$ nhỏ nhất có thể. Nhận thấy rằng, càng tăng $i$ thì $a_i$ càng lớn, nên chỉ số $j$ cần tìm chỉ có giảm chứ không có tăng. Do đó, với mỗi lần tăng $i$ ta chỉ việc kiểm tra xem $ps$ có thể giảm tiếp hay không:
while (ps > i && a[ps] + a[i] >= l) ps--; – chừng nào $a_{ps}$ ghép với $a_i$ vẫn còn $\ge L$ thì lùi $ps$ (tìm phần tử nhỏ hơn mà vẫn đủ $L$). Khi dừng, $a_{ps+1}$ là phần tử nhỏ nhất (sau $i$) ghép với $a_i$ được tổng $\ge L$.if (ps + 1 <= n && ps + 1 > i && a[ps + 1] + a[i] <= r) ans = min(ans, a[ps + 1] + a[i]);Con trỏ $i$ chỉ đi tới, con trỏ $ps$ chỉ đi lùi, mỗi con trỏ đi tối đa $n$ bước – nên phần hai con trỏ chỉ tốn $O(n)$.
while có điều kiện ps > i nên $ps$ có thể dừng đúng bằng $i$; sang các vòng $i$ sau thì $ps \lt i$ và điều kiện ps + 1 > i làm ta không xét gì nữa. Có bị sót đáp án không? Không đâu: $ps$ tụt về $i_0$ nghĩa là $a_{i_0} + a_{i_0+1} \ge L$ và cặp này đã được xét. Mọi cặp $(i, j)$ sau đó ($i_0 \lt i \lt j$) đều có tổng $\ge a_{i_0} + a_{i_0+1}$ – tức không thể nhỏ hơn ứng viên đã xét, nên bỏ qua cũng không sao. (Mình đã kiểm tra kỹ bằng so sánh với code vét cạn, xem ghi chú cuối bài.)Minh hoạ hai con trỏ
Em nhập $L$, $R$ và dãy giá rồi bấm Tiếp: ô vàng là $a_i$, ô tím là $a_{ps}$ đang thử, ô viền xanh là ứng viên $a_{ps+1}$.
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 n, l, r, a[1000005];
namespace sub2{
int solve(){
int ans = 2e9;
sort(a + 1, a + 1 + n);
int ps = n;
for (int i = 1; i <= n; i ++){
while (ps > i && (a[ps] + a[i]) >= l) ps --;
if ((ps + 1) <= n && (ps + 1) > i && a[ps + 1] + a[i] <= r){
ans = min(ans, a[ps + 1] + a[i]);
}
}
return ans;
}
};
int main(){
if(fopen("MUASAM.inp", "r")){
freopen("MUASAM.inp", "r", stdin);
freopen("MUASAM.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l >> r;
for (int i = 1; i <= n; i ++) cin >> a[i];
cout << sub2::solve() << endl;
}import sys, os
def solve(n, l, r, a):
ans = 2 * 10**9
a[1:] = sorted(a[1:])
ps = n
for i in range(1, n + 1):
while ps > i and a[ps] + a[i] >= l:
ps -= 1
if ps + 1 <= n and ps + 1 > i and a[ps + 1] + a[i] <= r:
ans = min(ans, a[ps + 1] + a[i])
return ans
if os.path.exists("MUASAM.inp"):
sys.stdin = open("MUASAM.inp", "r")
sys.stdout = open("MUASAM.out", "w")
data = sys.stdin.buffer.read().split()
n, l, r = int(data[0]), int(data[1]), int(data[2])
a = [0] + [int(x) for x in data[3:3 + n]]
print(solve(n, l, r, a))Giải thích 1 số chỗ trong code ở trên:
sort(a + 1, a + 1 + n);: sắp xếp các phần tử $a[1..n]$ tăng dần (mảng mình dùng chỉ số từ $1$).- Điều kiện
(ps + 1) <= n: nếu $ps$ chưa lùi lần nào (ngay cả phần tử lớn nhất ghép với $a_i$ vẫn $\lt L$) thì $ps + 1 = n + 1$ – không có ứng viên. Điều kiện(ps + 1) > i: sản phẩm thứ hai phải khác (và đứng sau) sản phẩm thứ nhất. - Ở đây mình dùng mảng tĩnh
a[1000005]khai báo toàn cục, đủ cho $N \le 10^6$.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: phần hai con trỏ là $O(N)$ vì $i$ chỉ tăng, $ps$ chỉ giảm. Cộng thêm bước sắp xếp $O(N \log N)$ nên tổng cộng là $O(N \log N)$. Mình đo bản C++ với $N = 10^6$ chạy khoảng 0.3 giây (tính cả đọc dữ liệu).
lower_bound(a + i + 1, a + n + 1, l - a[i]) để tìm ngay $j$ nhỏ nhất ($j \gt i$) có $a_j \ge L - a_i$, rồi kiểm tra $a_i + a_j \le R$. Cách này tốn $O(N \log N)$, cũng đủ nhanh. Hai con trỏ thì phần duyệt chỉ $O(N)$ và không cần nhớ hàm thư viện.sys.stdin.buffer) chạy khoảng 2 giây – có thể bị TLE nếu giới hạn 1 giây. Trong phòng thi HSG thì nên dùng C++ cho bài có $N$ cỡ $10^6$ nhé.- 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