Hướng dẫn giải của [VT Thiếu nhi] BÀI 13: MILKTEA
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Với mỗi ngày có số tiền ~m_i~, đếm số cửa hàng có giá ~x_j \le m_i~. Với ~n, q \le 10^5~, dùng sắp xếp giá rồi tìm nhị phân cho mỗi ngày.
Sub 1: Vét cạn — ~O(n \cdot q)~, dùng khi ~n \cdot q \le 10^8~
Mỗi ngày duyệt toàn bộ cửa hàng và đếm giá không vượt quá ~m_i~. Nếu chỉ nộp sub này: đúng 2/20 test (18 test còn lại quá giờ).
Sub 2: Sắp xếp và upper_bound — ~O((n + q) \log n)~
Sắp xếp giá, số cửa hàng có giá ~\le m_i~ chính là vị trí ~upper_bound(m_i)~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu. Nếu ~n \cdot q \le 10^8~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<long long> X, M;
// Sub 1: vet can. Moi ngay duyet tat ca cua hang, dem gia <= m. O(n*q). Dung khi n*q <= 10^8.
void sub1() {
for (int i = 0; i < q; i++) {
int cnt = 0;
for (int j = 0; j < n; j++)
if (X[j] <= M[i]) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: sap xep gia, dung upper_bound: so cua hang co gia <= m. O((n + q) log n).
void sub2() {
sort(X.begin(), X.end());
for (int i = 0; i < q; i++) {
int cnt = upper_bound(X.begin(), X.end(), M[i]) - X.begin();
cout << cnt << "\n";
}
}
int main() {
freopen("MILKTEA.INP", "r", stdin);
freopen("MILKTEA.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
X.resize(n);
for (int i = 0; i < n; i++) cin >> X[i];
cin >> q;
M.resize(q);
for (int i = 0; i < q; i++) cin >> M[i];
if ((long long)n * q <= 100000000) sub1(); // ~10^8 phep so sanh: chay duoi 1 giay
else sub2();
return 0;
}
Bình luận