Tiệm Sách
Đề bài
Nhà sách thành phố đang có chương trình ưu đãi "mua 3 lấy tiền 2 quyển đắt hơn". Tất nhiên khách hàng cũng có thể mua ít hơn hoặc nhiều hơn 3 quyển và tùy thuộc vào cách mua: 3 cuốn sách 1 lượt, cuốn rẻ nhất sẽ được miễn phí.
Giả sử anh Hiểu muốn mua 7 quyển sách có giá là: $2, 3, 4, 4, 6, 9, 10$. Nếu:
- Lượt 1 anh mua 3 quyển có giá $10, 3, 2$ thì quyển có giá $2$ sẽ được miễn phí.
- Lượt 2 anh mua 3 quyển có giá $6, 4, 4$ thì quyển có giá $4$ sẽ được miễn phí.
- Lượt 3 anh mua 1 quyển có giá $9$ thì hiển nhiên sẽ không được miễn phí quyển nào vì chỉ mua 1 quyển sách.
Yêu cầu: Tính số tiền nhỏ nhất phải trả cho $n$ quyển sách.
Dữ liệu vào:
- Dòng đầu là số tự nhiên $n$ $(n \le 10^5)$.
- Dòng thứ hai gồm $n$ số tự nhiên $a_i$ là giá của cuốn sách thứ $i$ $(1 \le a_i \le 10^6)$.
Dữ liệu ra: Gồm 1 số duy nhất là số tiền ít nhất phải trả cho $n$ cuốn sách.
Subtask:
- 20% số test đầu tiên có $n \le 20$.
- 30% số test tiếp theo có $n \le 10^3$.
- 20% số test tiếp theo có $n \le 10^4$.
- 30% số test còn lại không có giới hạn gì thêm.
6
6
4
5
5
5
521Giải thích ví dụ: sắp giá giảm dần được $6, 5, 5, 5, 5, 4$. Lượt 1 mua $6, 5, 5$ miễn phí một cuốn $5$; lượt 2 mua $5, 5, 4$ miễn phí cuốn $4$. Số tiền phải trả là $6 + 5 + 5 + 5 = 21$.
Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức làm, kèm thêm lời giải chi tiết để bạn nào không giải quyết được thì có thể tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn. Chúc các bạn học tốt và gặt hái nhiều thành công 😇.
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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngTư tưởng tham lam (Greedy)
Bài này dùng tư tưởng tham lam để giải quyết. Kể cả bạn nào không biết về tư tưởng tham lam thì thực ra đôi khi các bạn đang giải quyết vấn đề theo chính tư tưởng của tham lam mà các bạn không biết đó. Cho bạn nào chưa biết thì mình có thể nói nhanh thế này:
Thì tại sao bài này lại có thể nhìn ra tư tưởng tham lam? Đọc đề bài là thấy rõ mùi rồi hehe: muốn mua đủ $N$ quyển sách nhưng dựa theo chính sách giảm giá của cửa hàng thì phải làm sao để số tiền phải trả là ít nhất. Đọc kiểu này phát thấy mùi tham lam ngay 😝 Lúc nào cũng muốn phải ngon, phải bổ nhưng phải… rẻ 🤪
Tham lam chỉ là dạng tư tưởng thôi, còn để hiện thực được nó thì có thể cần đến những kỹ thuật bổ trợ khác nữa, như trong chính bài này là sắp xếp.
Chiến lượcCuốn được miễn phí phải đắt nhất có thể
Theo chính sách giảm giá, cứ 3 cuốn đưa ra tính tiền thì được giảm tiền của cuốn có giá thấp nhất. Vậy muốn mua $N$ cuốn thì ta cứ gom ra 3 cuốn làm 1 nhóm và đem ra tính tiền nhóm đó. Muốn số tiền phải trả ít nhất thì đồng nghĩa số tiền được giảm phải nhiều nhất, nó tỷ lệ nghịch với nhau thôi. Và để số tiền được giảm nhiều nhất thì cuốn sách được miễn phí trong mỗi nhóm 3 cuốn phải có giá lớn nhất có thể.
- Trong $N$ cuốn, xét ra 3 cuốn có giá lớn nhất, lớn nhì, lớn ba. Cuốn lớn ba sẽ không phải tính tiền (vì trong 3 cuốn đó nó rẻ nhất), và đó cũng là cuốn có số tiền được giảm lớn nhất có thể.
- Loại 3 cuốn vừa xét ra, tiếp tục xét 3 cuốn lớn nhất, nhì, ba trong $N - 3$ cuốn còn lại, cuốn lớn thứ 3 lại được giảm.
- Cứ như thế khi nào không gom được nhóm 3 nữa thì dừng. Những cuốn không được giảm cộng tổng lại chính là số tiền ít nhất phải trả.
Thử với 7 cuốn trong đề $2, 3, 4, 4, 6, 9, 10$: cách mua trong đề phải trả $10 + 3 + 6 + 4 + 9 = 32$. Còn theo tham lam: nhóm $(10, 9, 6)$ miễn phí cuốn $6$, nhóm $(4, 4, 3)$ miễn phí cuốn $3$, còn lại cuốn $2$, chỉ phải trả $10 + 9 + 4 + 4 + 2 = 29$.
Cài đặtSắp xếp giảm dần, bỏ qua các chỉ số 2, 5, 8…
Quy trình cứ trong tập các cuốn còn lại đi tìm 3 cuốn có giá lớn nhất, nhì, ba, thì để đơn giản ngay từ đầu ta đi sắp xếp tất cả $N$ cuốn theo giá giảm dần. Rồi cứ thế 3 cuốn đầu tiên chính là 3 cuốn có giá lớn nhất, 3 cuốn tiếp theo sẽ là 3 cuốn lớn nhất trong $N - 3$ cuốn còn lại, vì mảng đã sắp giảm dần nên đảm bảo được trật tự.
Đến đây là rất rõ ràng rồi nhưng vẫn sẽ có những bạn code phức tạp chỗ này lắm. Ta có thể nhìn ra như sau: duyệt từ index 0 trở đi thì 3 cuốn đầu là index $0, 1, 2$, rồi $3, 4, 5$, rồi $6, 7, 8$… Với $0, 1, 2$ thì cuốn miễn phí là index $2$; với $3, 4, 5$ là index $5$; với $6, 7, 8$ là index $8$. Các bạn có nhìn ra điều gì đặc biệt của các index $2, 5, 8, 11, 14, 17, 20\dots$ không?
| index i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| giá a[i] | 6 | 5 | 5 | 5 | 5 | 4 |
| i + 1 | 1 | 2 | 3 ✔ | 4 | 5 | 6 ✔ |
Ví dụ đề sau khi sắp giảm dần: các ô đỏ (index 2 và 5) là cuốn được miễn phí, cộng các ô xanh: $6 + 5 + 5 + 5 = 21$.
Vậy sau khi sắp xếp mảng giảm dần, ta duyệt từ index 0 trở đi: index nào cộng thêm 1 mà không chia hết cho 3 thì tính tiền (cộng vào biến sum), còn index nào cộng thêm 1 chia hết cho 3 thì bỏ qua vì đó là cuốn được miễn phí. Sau cùng biến sum là số tiền ít nhất phải trả theo chiến lược tham lam hehe 😁
Em nhập giá các cuốn sách rồi bấm Tiếp để xem từng lượt mua:
100%Code O(N log N) với hàm sort của STL
Source code các bạn tham khảo để nhìn thấy rõ tất cả những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n, greater<int>());
long long sum = 0;
for(int i = 0; i < n; ++i){
if((i + 1) % 3 != 0){
sum += a[i];
}
}
cout << sum;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted(map(int, data[1:n + 1]), reverse=True)
total = 0
for i in range(n):
if (i + 1) % 3 != 0:
total += a[i]
print(total)Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài cần nhập xuất nhiều, như bài này có tới $10^5$ số cần đọc vào mà giới hạn thời gian chỉ 100 ms, ta hãy nên để 2 dòng này vào để chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.sort(a, a + n, greater<int>()): sắp xếp $n$ phần tử đầu của mảng $a$ theo thứ tự giảm dần (mặc địnhsortsắp tăng dần, thêmgreater<int>()để đảo chiều).- Biến
sumphải làlong long: tổng có thể lên tới khoảng $\frac{2}{3} \cdot 10^5 \cdot 10^6 \approx 6{,}7 \cdot 10^{10}$, vượt xa giới hạn củaint(khoảng $2{,}1 \cdot 10^9$).
Thời gian gồm $O(N)$ đọc dữ liệu + $O(N \log N)$ sắp xếp bằng hàm sort trong STL + $O(N)$ duyệt tính tiền. Theo quy tắc cộng BigO ta lấy đại diện theo thành phần lớn nhất nên độ phức tạp tổng quát là $O(N \log N)$.
Đề bài này giới hạn chạy tối đa trong 100 ms thì ngưỡng tối đa sẽ là $(3 \text{ đến } 5) \cdot 10^6$ phép tính, cao lắm là $10^7$. Với $N$ lớn nhất là $10^5$ thì số lần lặp chỉ cỡ $10^5 + 10^5 \cdot \log_2(10^5) + 10^5$ $\approx 19 \cdot 10^5$, làm tròn dư dả là $2 \cdot 10^6$, yên tâm chưa vượt ngưỡng nên sẽ không sợ bị TLE.
Cẩn thậnDùng sắp xếp O(N²) thì sao?
Có thể nói phức tạp nhất của cách làm này là ở bước sắp xếp mảng giảm dần. Nếu bạn nào không dùng những thuật toán sắp xếp tối ưu mà dùng những thuật toán như Bubble Sort, Interchange Sort, Selection Sort… với độ phức tạp $O(N^2)$ thì bảo đảm TLE ngay với giới hạn 100 ms của bài này. Thậm chí có là giới hạn 1000 ms (1 giây) như thường lệ thì vẫn TLE luôn, bởi với $N = 10^5$ thì $N^2 = 10^{10}$ quá ngưỡng 1 giây rồi.
Để các bạn thấy rõ, mình viết thêm bản dùng Interchange Sort (đổi chỗ trực tiếp) thay cho hàm sort, phần còn lại giữ nguyên:
Code dùng Interchange Sort O(N²) – chỉ qua các subtask nhỏ
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n - 1; ++i){
for(int j = i + 1; j < n; ++j){
if(a[i] < a[j]){
swap(a[i], a[j]);
}
}
}
long long sum = 0;
for(int i = 0; i < n; ++i){
if((i + 1) % 3 != 0){
sum += a[i];
}
}
cout << sum;
return 0;
}import sys
data = sys.stdin.read().split()
n = int(data[0])
a = [int(x) for x in data[1:n + 1]]
for i in range(n - 1):
for j in range(i + 1, n):
if a[i] < a[j]:
a[i], a[j] = a[j], a[i]
total = 0
for i in range(n):
if (i + 1) % 3 != 0:
total += a[i]
print(total)Trên máy mình bản này chạy khoảng 0.06 giây với $N = 10^4$ (nên chỉ ăn được các subtask đầu, cỡ 50% đến 70% số test tuỳ máy chấm), còn với $N = 10^5$ thì mất tới hơn 13 giây!
Vì thế phải dùng những thuật toán sắp xếp tối ưu như Quick Sort, Merge Sort, Heap Sort với độ phức tạp $O(N \log N)$ thì mới đảm bảo được. Bình thường thì mình dùng luôn hàm sort có trong thư viện STL C++, nhanh gọn gọi 1 dòng ra xài thôi 🥰, chứ tự code thì vừa dài mà còn có thể sai, hoặc ví dụ Quick Sort nếu rơi vào trường hợp xấu nhất thì độ phức tạp vẫn là $O(N^2)$ nhé. Còn hàm sort trong STL C++ luôn đảm bảo $O(N \log N)$ trong mọi trường hợp: nó dùng thuật Intro Sort, là sự kết hợp, mặc định dùng Quick Sort nhưng nếu phát hiện rơi vào trường hợp xấu thì tự chuyển qua Heap Sort.
sort chạy khoảng 0.015 giây, bản Python khoảng 0.06 giây; kết quả lớn nhất $66\,667\,000\,000$ (khi mọi cuốn giá $10^6$) xác nhận phải dùng long long.
Nhận xét
Đăng nhận xét