Hướng dẫn giải của Bánh sinh nhật
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Editorial for birthcake: Bánh sinh nhật
Hiểu bài toán
Bài toán yêu cầu tìm số lượng bánh ngọt lớn nhất có thể ăn trong thời gian T giây. Bắt đầu tại tọa độ 0, Bờm di chuyển đến vị trí các bánh với thời gian |a - b| và ăn bánh tại đó với thời gian ti. Input được sắp xếp tăng dần theo tọa độ xi. Với N ≤ 10^5 và T, xi, ti ≤ 10^9, chúng ta cần một giải pháp hiệu quả O(N log N).
Các cách tiếp cận
Cách Quy hoạch động (Dynamic Programming)
// Phức tạp O(N^2), chỉ phù hợp N nhỏ
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; long long T;
cin >> n >> T;
vector<long long> x(n), t(n);
for(int i=0; i<n; i++) cin >> x[i] >> t[i];
// dp[i][j]: j=0 (không ăn i), j=1 (ăn i và quay về 0), j=2 (ăn i và đứng lại)
// ... (chi tiết quá dài, đây là minh họa ý tưởng)
// Giải pháp này O(N^2) hoặc O(N*K) không khả thi.
cout << 0;
return 0;
}
- Time Complexity: O(N^2)
- Space Complexity: O(N)
Có thể dùng DP dựa trên các mốc tọa độ. Tuy nhiên, do N lớn, các giải pháp DP thông thường sẽ quá chậm. Các solution được cung cấp sử dụng kỹ thuật hai con trỏ và cấu trúc dữ liệu ưu tiên để tối ưu.
Cách Hai con trỏ và Max-Heap (Duyệt Left)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; long long T;
cin >> n >> T;
vector<long long> x(n), t(n);
for (int i = 0; i < n; i++) cin >> x[i] >> t[i];
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int a, int b){ return x[a] < x[b]; });
multiset<long long> S;
long long sumT = 0;
int ans = 0;
int L = 0;
for (int R = 0; R < n; R++) {
S.insert(t[id[R]]);
sumT += t[id[R]];
while (L <= R) {
long long xmin = x[id[L]], xmax = x[id[R]];
// Công thức thời gian: Di chuyển liên tục từ L sang R, rồi về 0
// Hoặc từ 0 -> min -> max -> 0 (hoặc ngược lại).
// Công thức tối ưu: (xmax - xmin) + min(abs(xmin), abs(xmax))
long long travel = (xmax - xmin) + min(abs(xmin), abs(xmax));
long long need = travel + sumT;
if (need <= T) break;
// Nếu quá thời gian, loại bỏ bánh có t_i lớn nhất
auto it = prev(S.end());
sumT -= *it;
S.erase(it);
// Nếu loại bỏ hết bánh ở L, tăng L
if (S.empty()) {
L = R + 1;
break;
}
// Kiểm tra xem có nên loại bỏ bánh ở L không?
// Trong solution code, họ chỉ loại bỏ max t_i.
// Tuy nhiên, nếu sau khi loại max t_i vẫn quá, ta cần loại thêm.
// Hoặc nếu L không còn trong S (do bị xóa), ta phải tăng L.
}
// Cập nhật L: Nếu L không nằm trong S, ta phải tìm L mới.
// Code mẫu: while (L <= R && S.find(t[id[L]]) == S.end()) L++;
// Tuy nhiên, code mẫu dùng multiset và xóa max.
// Nếu xóa max mà vẫn quá, vòng while bên trong tiếp tục.
// Nếu xóa hết, vòng while bên trong break (do S.empty).
// Vòng lặp ngoài chỉ cập nhật ans = max(ans, S.size())
ans = max(ans, (int)S.size());
}
cout << ans;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Giải pháp này (Solution 1) sử dụng kỹ thuật hai con trỏ (L, R) để duyệt qua các đoạn liên tục các bánh được chọn. Với mỗi R, ta thêm bánh vào multiset (cần thiết để lấy max ti). Nếu tổng thời gian (di chuyển + t tổng) vượt T, ta lần lượt loại bỏ những bánh có ti lớn nhất trong đoạn đang xét cho đến khi thỏa mãn. Vấn đề của cách này là khi thay đổi L, ta cần xử lý multiset cho đúng (xóa các bánh ở L cũ nếu không còn trong đoạn).
Cách Hai con trỏ và Max-Heap (Duyệt Right - Optimal)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll T;
cin >> N >> T;
vector<pair<ll,ll>> A(N);
for(int i = 0; i < N; i++){
cin >> A[i].first >> A[i].second;
}
ll time_spent = 0;
ll pos_prev = 0;
priority_queue<ll> pq; // Max-heap
int best = 0;
for (int i = 0; i < N; i++) {
ll x = A[i].first;
ll t = A[i].second;
// Di chuyển từ vị trí trước đó đến x
time_spent += abs(x - pos_prev);
pos_prev = x;
// Thêm bánh hiện tại
time_spent += t;
pq.push(t);
// Nếu vượt quá T, loại bỏ bánh ăn lâu nhất
while (!pq.empty() && time_spent > T) {
ll bad = pq.top(); pq.pop();
time_spent -= bad;
}
// Cập nhật kết quả
best = max(best, (int)pq.size());
}
cout << best;
return 0;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Đây là giải pháp tối ưu nhất (Solution 2). Nó giả định rằng quãng đường di chuyển hiệu quả nhất để ăn k bánh bất kỳ là đi qua chúng theo thứ tự tọa độ (vì input đã được sắp xếp). Khi duyệt qua từng bánh từ trái sang phải (R), ta thêm bánh vào danh sách ăn. Nếu tổng thời gian (di chuyển từ R-1 sang R + t[R] + t tổng) vượt T, ta loại bỏ bánh có ti lớn nhất trong danh sách đã chọn. Cách này đảm bảo ta luôn giữ lại nhiều bánh nhất có thể với tổng ti nhỏ nhất cho quãng đường di chuyển hiện tại.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N^2) | O(N) | Quy hoạch động (Dynamic Programming) |
| 2 | O(N log N) | O(N) | Hai con trỏ và Max-Heap (Duyệt Left) |
| 3 | O(N log N) | O(N) | Hai con trỏ và Max-Heap (Duyệt Right - Optimal) |
Bài học kinh nghiệm
- Input được sắp xếp theo tọa độ, gợi ý việc duyệt tuần tự từ trái sang phải.
- Để tối đa hóa số lượng bánh, ta nên ưu tiên chọn những bánh có thời gian ăn t_i nhỏ nhất.
- Thời gian di chuyển giữa các bánh đã chọn (theo thứ tự tọa độ) là cố định và không phụ thuộc vào thứ tự ăn (nếu đi liên tục), chính là quãng đường từ bánh đầu đến bánh cuối cộng với quãng về 0 (hoặc quãng từ 0 đến cận gần nhất).
Lỗi thường gặp
- Lầm tưởng về thời gian di chuyển: Nếu chọn các bánh không liên tục (ví dụ chọn bánh 1 và bánh 3 nhưng bỏ bánh 2), thời gian di chuyển vẫn là |x1 - x3| (vì đi đường thẳng).
- Quên xử lý overflow khi tính tổng thời gian (T và các giá trị lên tới 10^9, tích có thể lên tới 10^18, cần dùng long long).
- Sử dụng vector thay vì priority queue trong khi cần liên tục tìm và xóa phần tử lớn nhất sẽ làm tăng độ phức tạp.
Bình luận