Khuyến mãi trà sữa
Đề bài
Nhân dịp sinh nhật, Lazada tổ chức chương trình khuyến mãi trà sữa cho khách hàng. Mỗi lượt khuyến mãi sẽ có tất cả $\mathbf{n}$ ly trà sữa được chế biến, với giá tiền mỗi ly đã được khuyến mãi là $\mathbf{b_i}$. Do số lượng trà sữa có hạn, nên $\mathbf{n}$ vị khách ngẫu nhiên sẽ được lựa chọn để tham gia chương trình, và số tiền mỗi người có thể chi trả cho việc mua trà sữa là $\mathbf{a_i}$.
Ban đầu mỗi người chơi sẽ được chỉ định để mua ly trà sữa đúng với vị trí của mình. Tuy nhiên, để tăng tính tương tác cho khách hàng và đảm bảo công bằng, Lazada quyết định tổ chức khuyến mãi theo hình thức ghép cặp người chơi. Một cặp đôi 'tốt' được định nghĩa là tổng số tiền họ bỏ ra để mua trà sữa phải lớn hơn tổng giá tiền hai ly trà sữa tại vị trí tương ứng, hay nói cách khác là $\mathbf{a_i + a_j > b_i + b_j}$với hai người tham gia tại vị trí$i$ và $j$.
Lazada muốn biết trước rằng có thể có bao nhiêu cặp đôi tốt tham gia được chương trình khuyến mãi. Lưu ý rằng mỗi người có thể ghép cặp được với nhiều người chơi khác và không nhất thiết phải có điều kiện: $a_i > b_i, \forall i: 1 \le i \le n$.
Các bạn cài đặt chương trình để giúp Lazada giải quyết vấn đề trên, sẽ có hai mức điểm cho câu hỏi này:
Subtask:
- 50% số test đầu tiên có $n \le 10^4$.
- 50% số test còn lại không có giới hạn gì thêm.
Đầu vào:
- Dòng đầu tiên quy định số ly trà sữa được chế biến hay số người được tham gia chương trình, là số nguyên $n$ thỏa $2 \le n \le 2 \cdot 10^5$.
- Dòng tiếp theo bao gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^6)$, trong đó $a_i$ là số tiền của mỗi người chơi bỏ ra để tham gia chương trình.
- Dòng tiếp theo bao gồm $n$ số nguyên $b_1, b_2, \dots, b_n$ $(1 \le b_i \le 10^6)$, trong đó $b_i$ là giá tiền được khuyến mãi của mỗi ly trà sữa.
Đầu ra: Yêu cầu đầu ra của chương trình là tổng số cặp đôi 'tốt' có thể tham gia khuyến mãi, là một số nguyên.
4
3 2 4 5
2 3 6 414
3 2 4 5
2 2 6 43Giải thích ví dụ 1: chỉ có một cặp đôi tốt là người chơi thứ 1 và người chơi cuối cùng, thỏa mãn $a_1 + a_4 = 8 > 6 = b_1 + b_4$.
Giải thích ví dụ 2: có ba cặp đôi tốt là người chơi thứ 1 và người chơi cuối cùng, thỏa mãn $a_1 + a_4 = 8 > 6 = b_1 + b_4$; người chơi thứ 1 và người chơi thứ hai,$ $thỏa mãn$a_1 + a_2 = 5 > 4 = b_1 + b_2$; người chơi thứ 2 và người chơi cuối cùng,$ $thỏa mãn$a_2 + a_4 = 7 > 6 = b_2 + b_4$.
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 😇.
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:
50%Subtask 1: vét cạn mọi cặp O(N²)
Với Subtask 1 (50% test đầu tiên) cài đặt với thuật $O(N^2)$ thì quá đơn giản rồi, nó là vét cạn xét hết tất cả các cặp có thể thôi: 2 vòng lặp for lồng nhau giống các thuật toán sắp xếp mảng cơ bản mà bạn nào mới học mảng cũng biết đó (Bubble Sort, Interchange Sort). Với mỗi cặp $(i, j)$, $i < j$ ta kiểm tra $a_i + a_j > b_i + b_j$ thì tăng biến đếm.
Đây mình code nhanh ra để các bạn tham khảo, vì nó quá cơ bản rồi nên mình sẽ không giải thích gì thêm nhé 🤪
Code Subtask 1 – vét cạn O(N²)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5;
int a[MAX + 5], b[MAX + 5];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
cin >> b[i];
}
long long cnt = 0;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(a[i] + a[j] > b[i] + b[j]){
cnt++;
}
}
}
cout << cnt;
return 0;
}import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt = 0
for i in range(n):
ai = a[i]
bi = b[i]
for j in range(i + 1, n):
if ai + a[j] > bi + b[j]:
cnt += 1
print(cnt)Có $\frac{N(N-1)}{2}$ cặp. Với $N = 10^4$ là khoảng $5 \cdot 10^7$ phép so sánh, vẫn qua được 1 giây; nhưng với $N = 2 \cdot 10^5$ thì lên tới $2 \cdot 10^{10}$, chắc chắn TLE. Lưu ý biến đếm là long long vì số cặp có thể tới gần $2 \cdot 10^{10}$, vượt giới hạn int.
Mấu chốtChuyển vế: chỉ còn 1 mảng số tiền còn lại
Với Subtask 2 (Full test) thì phải code với thuật $O(N \log N)$ thì mới AC, cái này mới khó hơn đòi hỏi tư duy nhiều hơn. Để đếm xem tổng cộng có bao nhiêu cặp có tổng tiền hiện có lớn hơn tổng giá tiền của 2 ly trà sữa tương ứng của 2 người đó, thay vì phải xét qua lần lượt tất cả các cặp như cách làm ở trên thì muốn giải quyết tối ưu hơn ta phải nhìn ra mấu chốt sau:
Thì ta có thể tính xem số tiền còn lại của từng người sau khi trả cho ly trà sữa tương ứng của người đó, tức là a[i] -= b[i]. Tận dụng luôn mảng a đã có khỏi mất công đi tạo mảng mới. Mảng a giờ đây không còn là mảng chứa số tiền ban đầu của mỗi người mà là số tiền còn lại của mỗi người sau khi đã trả cho ly trà sữa của mình.
| Người | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| a (tiền có) | 3 | 2 | 4 | 5 |
| b (giá ly) | 2 | 2 | 6 | 4 |
| a − b (còn lại) | 1 | 0 | -2 | 1 |
| Sau khi sắp tăng dần | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| a | -2 | 0 | 1 | 1 |
Ví dụ 2: số tiền còn lại là $1, 0, -2, 1$. Các cặp có tổng $\ge 1$: $(1, 0)$ của người 1 và 2, $(1, 1)$ của người 1 và 4, $(0, 1)$ của người 2 và 4 → đúng 3 cặp như đề.
Ý tưởngSắp xếp tăng dần + tìm kiếm nhị phân
Rồi thì đếm xem với số tiền còn lại này sẽ có thể bắt cặp được với số tiền còn lại của bao nhiêu người đằng sau vị trí người đang xét hiện tại để tổng số tiền còn lại của 2 người sẽ từ 1 trở lên. Vậy sau khi tính ra số tiền còn lại của mỗi người, ta đi sắp xếp tăng dần. Rồi xét lần lượt a[i] là số tiền còn lại của người thứ $i$ thì ta sẽ đếm xem đằng sau đó (từ a[i + 1] đến cuối, tức là a[n - 1]) có bao nhiêu người có số tiền còn lại $\ge 1 - a[i]$.
Điều này hết sức nhanh chóng khi mảng đã có thứ tự tăng dần: áp dụng tìm kiếm nhị phân để tìm ra vị trí index bé nhất của người đằng sau vị trí $i$ mà thoả $\ge 1 - a[i]$. Vì là vị trí bé nhất nên từ index đó đến cuối mảng toàn bộ đều là những người thoả mãn (mảng càng về sau càng lớn). Vậy số lượng tính nhanh bằng công thức n - idx.
Việc tìm kiếm nhị phân từ vị trí $i + 1$ trở về sau để tìm vị trí bé nhất thoả $\ge 1 - a[i]$ thì ta dùng hàm lower_bound có sẵn của thư viện STL trong C++ để giải quyết nhanh gọn. Bạn nào chưa biết cách dùng hàm này thì Google search tìm hiểu nhé, nó cũng đơn giản thôi.
Em nhập 2 dãy $a$, $b$ rồi bấm Tiếp để xem từng bước đếm:
100%Code O(N log N) với sort và lower_bound
Source code cho các bạn tham khảo để thấy rõ hơn những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5;
int a[MAX + 5], b[MAX + 5];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
cin >> b[i];
}
for(int i = 0; i < n; ++i){
a[i] -= b[i];
}
sort(a, a + n);
long long cnt = 0;
for(int i = 0; i < n; ++i){
int idx = lower_bound(a + i + 1, a + n, 1 - a[i]) - a;
if(idx != n){
cnt += n - idx;
}
}
cout << cnt;
return 0;
}import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n):
a[i] -= b[i]
a.sort()
cnt = 0
for i in range(n):
idx = bisect_left(a, 1 - a[i], i + 1, n)
cnt += n - idx
print(cnt)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 $4 \cdot 10^5$ số cần đọc vào, 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é.lower_bound(a + i + 1, a + n, 1 - a[i])tìm trong đoạna[i + 1..n - 1](đã tăng dần) phần tử đầu tiên $\ge 1 - a[i]$ và trả về con trỏ tới nó; trừ điata được index. Bản Python dùngbisect_left(a, 1 - a[i], i + 1, n)có ý nghĩa y hệt.if(idx != n): các bạn phải xem hiểu về cách sử dụng hàmlower_boundmới hiểu chỗ này nhé. Trong trường hợp không tìm thấy phần tử nào thoả mãn thì hàm sẽ trả về vị trí là $n$ (chính là số lượng phần tử của mảng), và lúc này ta hiểu là không tồn tại phần tử thoả mãn, bởi index hợp lệ là từ $0$ đến $n - 1$ nên index $n$ nghĩa là không hợp lệ. Nên ta chỉ xét những index trả về khác $n$ tức là có tồn tại. (Thực ra khiidx == nthìn - idx = 0, cộng vào cũng không sao, nên bản Python mình bỏ luôn câuif.)
Đánh giá độ phức tạp
Đầu tiên phải xét đến độ phức tạp của việc sắp xếp mảng tăng dần. Nếu bạn nào dùng những thuật như Bubble Sort, Interchange Sort hay Selection Sort với độ phức tạp $O(N^2)$ thì như vậy là không hợp lệ với yêu cầu của câu này rồi, các bạn phải dùng những thuật có độ phức tạp $O(N \log N)$ như Quick Sort, Merge Sort, Heap Sort nhé. Bình thường thì mình dùng hàm sort có trong thư viện STL C++ để độ phức tạp luôn đảm bảo $O(N \log N)$ và nhanh gọn gọi 1 dòng ra xài thôi, chứ tự code thuật thì vừa dài mà còn có thể sai, hoặc ví dụ Quick Sort nếu bị rơi vào trường hợp xấu nhất thì độ phức tạp cũng vẫn là $O(N^2)$. 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 nó sẽ tự chuyển qua Heap Sort.
Tiếp đó là xét duyệt qua lần lượt số tiền còn lại của mỗi người, bước này tốn $O(N)$; với mỗi giá trị a[i] đi tìm kiếm nhị phân bước này tốn $O(\log N)$ → bước này độ phức tạp cũng là $O(N \log N)$.
⇒ Tổng quát toàn hàm có độ phức tạp là $O(2N \log N)$, theo quy tắc BigO vẫn tính là $O(N \log N)$ và vẫn đúng như yêu cầu của đề.
long long.
Nhận xét
Đăng nhận xét