Ăn Buffet
Đề bài: AnBuffet – Ăn buffet
Đến năm 2030 Quảng Trị lúc này là một đô thị phát triển sầm uất, các quán cơm bụi đều chuyển loại hình thành các quán ăn buffet hiện đại tầm cỡ 3 sao.
Bin lúc này là một doanh nhân thành đạt với công ty mà anh lập ra. Nhân dịp hè gặp lại người bạn cùng hội là Nhin, anh đưa bạn mình ăn buffet tại nhà hàng Ý HẰNG.
Nhà hàng có $N$ món ăn được sắp xếp thành một hàng cố định trên bàn ăn. Quy định ăn buffet của quán có một điều khá đặc biệt: nếu khách hàng chọn được các món ăn có tổng trọng lượng tối thiểu là $u$ và không quá $v$ thì sẽ được đưa vào danh sách chọn thăm may mắn của quán. Ai là chủ nhân của lá thăm có tổng giá trị các món ăn lớn nhất thì sẽ nhận phiếu ăn buffet miễn phí trong 1 năm.
Bin và Nhin rất muốn giành được may mắn đó. Tuy nhiên công việc khá là khó vì có nhiều món ăn. Bạn hãy lập trình tính giúp cho hai bạn ấy.
Input
- Dòng đầu tiên ghi 3 số nguyên dương $N, U, V$ ($N \le 32$; $U, V \le 10^{18}$).
- $N$ dòng tiếp theo, mỗi dòng ghi hai số $w[i]$ và $v[i]$ là trọng lượng và giá trị của món ăn thứ $i$ (do khách hàng khá đông nên mỗi món chỉ còn duy nhất 1 cái) ($w[i], v[i] \le 10^{15}$).
Output: một dòng duy nhất là giá trị lớn nhất của các món ăn mà Bin và Nhin có thể chọn.
Ràng buộc
- 50% số test đầu tiên có $N \le 16$.
- 50% số test còn lại không có giới hạn gì thêm.
3 6 8
3 10
7 3
8 23Lờ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 CodeforcesTóm tắt đề bài một cách đơn giản nhất để bạn nào chưa hiểu: anh em được cho $N$ món ăn ($N \le 32$), mỗi món có trọng lượng $w[i]$ và giá trị $v[i]$ ($\le 10^{15}$). Mỗi món chỉ được ăn 1 lần; hãy in ra giá trị lớn nhất của các món ăn có thể chọn sao cho tổng trọng lượng tối thiểu là $U$ và không quá $V$ ($U, V \le 10^{18}$).
Ở ví dụ: $N = 3$, $U = 6$, $V = 8$, các món có {w, v} là {3, 10}, {7, 3}, {8, 2}. Kết quả là 3, tức là chọn ăn món số 2. Ta không thể chỉ ăn món số 1 vì tổng trọng lượng mới là 3 (nhỏ hơn 6); không thể ăn 2 hoặc cả 3 món bất kì vì khi đó tổng trọng lượng sẽ lớn hơn 8. Chọn món số 2 thì tổng trọng lượng thoả mãn $6 \le 7 \le 8$ và cho giá trị lớn nhất có thể là 3.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
50%Cách 1: quay lui vét cạn – O(2^N)
Bài này thì anh em sẽ thấy khá chi là giống bài cái túi ha: chọn các món sao cho giá trị lớn nhất và trọng lượng không vượt quá $V$; đặc biệt hơn là trọng lượng còn phải $\ge U$ nữa, và $N$ có thể lớn tới 32 lận. Giờ mình sẽ đi vào cách làm đơn giản nhất: quay lui vét cạn, thử mọi khả năng có thể.
Gọi hàm Try(i, wei, val) giúp ta thử mọi trường hợp, với $i$ là số thứ tự của món đang xét, wei là tổng trọng lượng các món đã chọn, val là tổng giá trị các món đã chọn. Ta tạo thêm 1 biến toàn cục res để lưu kết quả.
- Điều kiện dừng: khi $i = N + 1$ (đã lựa chọn xong cả $N$ món), ta kiểm tra
weicó $\ge U$ và $\le V$ không, nếu có thì cập nhậtres = max(res, val), rồireturn. - Xử lý: ở món thứ $i$ luôn có 2 lựa chọn là không ăn và có ăn: gọi
Try(i + 1, wei, val)(không ăn) vàTry(i + 1, wei + w[i], val + v[i])(có ăn).
Một lưu ý là anh em phải để kiểu dữ liệu $U$, $V$ và mảng $w$, $v$ là long long nha, để int là sẽ bị tràn số đó. Lúc đầu chưa chọn món nào nên gọi Try(1, 0, 0).
Xem code vét cạn (50% điểm)
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll N, U, V;
ll w[35], v[35];
ll res = 0;
void Try(int i, ll wei, ll val){
if(i == N + 1){
if(wei >= U && wei <= V){
res = max(res, val);
}
return;
}
Try(i + 1, wei, val);
Try(i + 1, wei + w[i], val + v[i]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> U >> V;
for(int i = 1; i <= N; ++i){
cin >> w[i] >> v[i];
}
Try(1, 0, 0);
cout << res;
return 0;
}import sys
sys.setrecursionlimit(10**5)
res = 0
def Try(i, wei, val):
global res, N, U, V, w, v
if i == N + 1:
if U <= wei <= V:
res = max(res, val)
return
Try(i + 1, wei, val)
Try(i + 1, wei + w[i], val + v[i])
N, U, V = map(int, input().split())
w = [0] * (N + 1)
v = [0] * (N + 1)
for i in range(1, N + 1):
w[i], v[i] = map(int, input().split())
Try(1, 0, 0)
print(res)Anh em có thể cải tiến hơn chút nữa: nếu tổng trọng lượng đã chọn cộng với w[i] mà $\gt V$ thì ta không gọi đệ quy chọn món đó nữa. Tức là chỉ khi wei + w[i] <= V thì mới gọi Try(i + 1, wei + w[i], val + v[i]). Từ đó luôn đảm bảo wei $\le V$, và khi $i = N + 1$ ta chỉ cần kiểm tra wei >= U nữa thôi:
void Try(int i, ll wei, ll val){
if(i == N + 1){
if(wei >= U){
res = max(res, val);
}
return;
}
Try(i + 1, wei, val);
if(wei + w[i] <= V){
Try(i + 1, wei + w[i], val + v[i]);
}
}Tuy độ phức tạp theo BigO không đổi nhưng sẽ có nhiều test hàm Try() trên chạy nhanh hơn nha.
Đánh giá độ phức tạp: không gian $O(N)$ (2 mảng $w$, $v$); thời gian $O(2^N)$ vì mỗi món có 2 lựa chọn. Trong 1 giây máy tính tính được khoảng $10^8$ phép tính, mà với $N = 32$ thì $2^{32} \approx 4.3$ tỉ phép tính, phải chạy mất cỡ 43 giây lận (mình chạy thử bản C++ mất khoảng 15 giây). Vậy cách trên sẽ bị TLE, giờ ta đến với cách làm tối ưu hơn để AC bài này nha.
100%Cách 2: chia đôi tập (meet in the middle)
Để làm được bài này đầu tiên anh em cần biết về kĩ thuật chia đôi tập (meet in the middle) nha, anh em nào chưa biết thì tham khảo ở VNOI Wiki – Meet in the middle. Đây là kĩ thuật tìm kiếm dùng cho những bài có đầu vào nhỏ, nhưng không nhỏ đến mức có thể vét cạn. Nó khá giống chia để trị: chia vấn đề thành 2, giải quyết riêng rẽ rồi hợp nhất lại. Nhưng khác ở chỗ sau khi chia ra làm 2 thì mỗi nửa không còn có cấu trúc giống bài toán ban đầu.
- Chia các món ra làm đôi: $N / 2$ món đầu một nửa, các món từ $N / 2 + 1$ đến $N$ là nửa còn lại.
- Vét cạn từng nửa: tìm tất cả các cặp {tổng trọng lượng, tổng giá trị} có thể có ở nửa đầu, lưu vào
vector<pair<long long, long long>> x; tương tự nửa sau lưu vàoy. Mỗi vector có tối đa $2^{N/2} = 2^{16} = 65536$ phần tử, đủ bé để lưu trữ thoải mái, và vét cạn $2^{16}$ trường hợp thì chạy rất nhanh. Khi lưu, ta chỉ giữ những cặp có trọng lượng $\le V$ (nếu một nửa đã quá $V$ thì cộng thêm nửa kia càng quá); còn nhỏ hơn $U$ thì vẫn giữ, vì nửa kia có thể bù vào cho đủ. - Hợp nhất: kết hợp các cặp
x[i]vày[j]sao chox[i].second + y[j].secondlớn nhất mà vẫn thoả $U \le$x[i].first + y[j].first$\le V$.
Nếu hợp nhất bằng 2 vòng for lồng nhau thì độ phức tạp là $O(2^{N/2} \cdot 2^{N/2}) = O(2^N)$, chẳng khác gì vét cạn. Cách để giảm độ phức tạp: sắp xếp vector x tăng dần theo trọng lượng, rồi chỉ cần 1 vòng for duyệt qua vector y. Với mỗi y[j], điều kiện được viết lại thành:
- Biên trái:
x[i].first >= U - y[j].first– dùnglower_bound(trả về phần tử đầu tiên $\ge$ giá trị cần tìm), trừ đix.begin()ra được vị tría. Vìxtăng dần nên mọi vị trí $\ge a$ đều thoả. - Biên phải:
x[i].first <= V - y[j].first– C++ không có hàm tìm "$\le$", nhưng cóupper_boundtrả về phần tử đầu tiên $\gt$ giá trị cần tìm, thì vị trí ngay trước nó chắc chắn $\le$. Vậy lấy vị trí đó rồi lùi lại 1 là đượcb. - Nhớ kiểm tra
a < nvàb >= 0nha: nếulower_boundtrả về cuối mảng thì không có phần tử nào thoả; nếub < 0thìupper_boundđã trả về đầu mảng.
Vậy ta có $a \le i \le b$. Không lẽ lại duyệt trâu từ $a$ tới $b$? Thế thì trường hợp xấu nhất lại là cả vector x. Vấn đề cần giải quyết là tìm x[i].second lớn nhất trong đoạn từ $a$ tới $b$, và đó chính là 1 trong những ứng dụng phổ biến nhất của Segment Tree: cho biết phần tử lớn nhất trong một đoạn chỉ với $O(\log_2(\text{x.size()}))$. Các bạn có thể đọc về Segment Tree tại VNOI Wiki – Segment Tree; trong đó có ví dụ bài toán tìm giá trị nhỏ nhất trên đoạn (RMQ), giờ mình cần lớn nhất thì chỉ cần sửa một chút thôi.
Với ví dụ $N = 3$, $U = 6$, $V = 8$: nửa đầu chỉ có món 1, nửa sau có món 2 và 3. Vector x (đã sắp theo trọng lượng) = (0, 0), (3, 10); vector y = (0, 0), (7, 3), (8, 2) (cặp chọn cả món 2 và 3 nặng 15 > V nên bị loại ngay từ lúc vét cạn).
| Phần tử y | Điều kiện cho x[i].first | Đoạn [a, b] trong x | Giá trị tốt nhất |
|---|---|---|---|
| (0, 0) | 6 − 0 = 6 ≤ x.first ≤ 8 − 0 = 8 | a = 2, b = 1 | không có |
| (7, 3) | 6 − 7 = -1 ≤ x.first ≤ 8 − 7 = 1 | a = 0, b = 0 | 0 + 3 = 3 |
| (8, 2) | 6 − 8 = -2 ≤ x.first ≤ 8 − 8 = 0 | a = 0, b = 0 | 0 + 2 = 2 |
Vậy với 2 lần tìm kiếm nhị phân và 1 lần truy vấn segment tree cho mỗi phần tử của y, bước hợp nhất tốn $O(2^{N/2} \cdot 3 \cdot N/2)$, với $N = 32$ chỉ khoảng $3.2 \cdot 10^6$ phép tính, chạy dưới 1 giây dễ dàng.
Mô phỏng: em nhập $U$, $V$ và các món (mỗi món "w v", cách nhau bởi dấu phẩy) rồi bấm Tiếp để xem từng bước: chia đôi, vét cạn mỗi nửa, sắp xếp $x$, rồi với mỗi cặp của $y$ tìm đoạn $x$ ghép được và lấy giá trị lớn nhất trong đoạn đó:
Cài đặt từng phần
Mình đã typedef long long ll; typedef pair<ll, ll> pll; nên pll chính là pair<long long, long long> nha.
1. Xây dựng 2 vector x, y. Thực ra không cần chia ra 2 mảng, chỉ cần sửa hàm Try() thành Try(int i, int des, ll wei, ll val, vector<pll> &res): $i$ là món đang xét, des là món cuối cùng phải xét, và vector res truyền tham chiếu để lưu các cặp {wei, val}. Nếu không có tham chiếu thì thứ truyền vào chỉ là bản sao, thay đổi bản sao thì bản gốc ở ngoài không được cập nhật, lại còn mất thời gian copy nữa.
void Try(int i, int des, ll wei, ll val, vector<pll> &res){
if(i == des + 1){
res.push_back((pll){wei, val});
return;
}
Try(i + 1, des, wei, val, res);
if(wei + w[i] <= V){
Try(i + 1, des, wei + w[i], val + v[i], res);
}
}vector<pll> x, y;
Try(1, N / 2, 0, 0, x);
Try(N / 2 + 1, N, 0, 0, y);Nửa đầu bắt đầu từ 1 tới $N / 2$ nên $i = 1$, des = N / 2, lưu vào x; nửa sau từ $N / 2 + 1$ tới $N$, lưu vào y. Lưu ý push_back((pll){wei, val}) phải ép kiểu dữ liệu nha.
2. Sắp xếp và hàm comp. Anh em thường nhớ khi sort các pair thì sắp theo .first; đúng nhưng chưa đủ: nếu .first bằng nhau thì nó sắp tiếp theo .second. Điều này có vẻ không ảnh hưởng, nhưng với upper_bound, lower_bound thì vô cùng nguy hiểm, nên mình khuyên viết hàm comp chỉ so sánh .first (truyền tham chiếu để tránh copy, có const để tránh bị thay đổi):
bool comp(const pll &a, const pll &b){
return a.first < b.first;
}
// sắp xếp vector x:
sort(x.begin(), x.end(), comp);3. Tìm 2 biên a, b. Vì x chứa các pair nên giá trị truyền vào lower_bound/upper_bound cũng phải là pair: {U − tmp.first, phần tử thứ 2} và {V − tmp.first, phần tử thứ 2}, mình chọn phần tử thứ 2 bằng 0 (ta đang duyệt for(pll tmp : y) nên tmp.first chính là y[j].first). Ở dòng tìm b, mình viết tắt --upper_bound(...): ngay khi có con trỏ trả về thì lùi lại 1, rồi trừ x.begin() ra vị trí.
int a = lower_bound(x.begin(), x.end(), (pll){U - tmp.first, 0}, comp) - x.begin();
int b = --upper_bound(x.begin(), x.end(), (pll){V - tmp.first, 0}, comp) - x.begin();
// hoặc viết tách ra cho dễ hình dung phần tìm b:
int b = upper_bound(x.begin(), x.end(), (pll){V - tmp.first, 0}, comp) - x.begin();
b--;comp, lower_bound với {c, d} trả về cặp đầu tiên có .first >= c, nhưng nếu có cặp .first == c thì nó còn so tiếp .second >= d; upper_bound cũng tương tự. Thử đoạn code dưới đây: ta muốn tìm phần tử đầu tiên có khối lượng > 1, tức là vị trí 3 là {2, 0}, nhưng nó lại in ra 2 (phần tử {1, 1}); còn lower_bound thì in ra 1 (phần tử {1, 0}) trong khi cần là {1, −1} ở vị trí 0.#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main(){
vector<pii> a;
a.push_back((pii){1, -1});
a.push_back((pii){1, 0});
a.push_back((pii){1, 1});
a.push_back((pii){2, 0});
cout << upper_bound(a.begin(), a.end(), (pii){1, 0}) - a.begin(); // in ra 2
// thử thay bằng dòng dưới thì sẽ in ra 1:
// cout << lower_bound(a.begin(), a.end(), (pii){1, 0}) - a.begin();
return 0;
}Chỉ cần truyền thêm hàm comp (sắp tăng dần theo .first) thì upper_bound cho ra vị trí 3 và lower_bound cho ra vị trí 0, đúng điều ta cần:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
bool comp(const pii &a, const pii &b){
return a.first < b.first;
}
int main(){
vector<pii> a;
a.push_back((pii){1, -1});
a.push_back((pii){1, 0});
a.push_back((pii){1, 1});
a.push_back((pii){2, 0});
cout << upper_bound(a.begin(), a.end(), (pii){1, 0}, comp) - a.begin(); // in ra 3
// còn lower_bound có comp sẽ in ra 0
return 0;
}4. Segment tree lấy max. Segment tree lưu trên mảng 1 chiều; mảng có $n$ phần tử thì cây cần mảng $4n$ là vừa đủ, nên với x tối đa $2^{16}$ phần tử ta khai báo st[4 * 2^16]. Hàm build chỉ cần thêm vector x vào để gán st[id] = x[l].second (giá trị ăn được); còn muốn lấy giá trị lớn nhất trong đoạn từ $a$ tới $b$ thì gọi maxVal(1, 0, n - 1, a, b), với cây được xây bằng build(1, 0, n - 1, x):
void build(int id, int l, int r, const vector<pll> &x){
if(l == r){
st[id] = x[l].second;
return;
}
int m = (l + r) / 2;
build(2 * id, l, m, x);
build(2 * id + 1, m + 1, r, x);
st[id] = max(st[2 * id], st[2 * id + 1]);
}
ll maxVal(int id, int l, int r, int a, int b){
if(l > b || r < a){
return LLONG_MIN;
}
if(l >= a && r <= b){
return st[id];
}
int m = (l + r) / 2;
return max(maxVal(2 * id, l, m, a, b), maxVal(2 * id + 1, m + 1, r, a, b));
}Các bạn nên tìm hiểu kỹ về segment tree thì sẽ hiểu sâu hơn đoạn code trên, vì để lý giải hết trong một bài viết thì khó có thể làm được.
Source code hoàn chỉnh
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int maxN = 1 << 16;
ll N, U, V;
ll w[35], v[35];
ll st[4 * maxN];
void build(int id, int l, int r, const vector<pll> &x){
if(l == r){
st[id] = x[l].second;
return;
}
int m = (l + r) / 2;
build(2 * id, l, m, x);
build(2 * id + 1, m + 1, r, x);
st[id] = max(st[2 * id], st[2 * id + 1]);
}
ll maxVal(int id, int l, int r, int a, int b){
if(l > b || r < a){
return LLONG_MIN;
}
if(l >= a && r <= b){
return st[id];
}
int m = (l + r) / 2;
return max(maxVal(2 * id, l, m, a, b), maxVal(2 * id + 1, m + 1, r, a, b));
}
void Try(int i, int des, ll wei, ll val, vector<pll> &res){
if(i == des + 1){
res.push_back((pll){wei, val});
return;
}
Try(i + 1, des, wei, val, res);
if(wei + w[i] <= V){
Try(i + 1, des, wei + w[i], val + v[i], res);
}
}
bool comp(const pll &a, const pll &b){
return a.first < b.first;
}
ll solve(){
vector<pll> x, y;
Try(1, N / 2, 0, 0, x);
Try(N / 2 + 1, N, 0, 0, y);
sort(x.begin(), x.end(), comp);
int n = (int)x.size();
build(1, 0, n - 1, x);
ll res = 0;
for(pll tmp : y){
int a = lower_bound(x.begin(), x.end(), (pll){U - tmp.first, 0}, comp) - x.begin();
int b = --upper_bound(x.begin(), x.end(), (pll){V - tmp.first, 0}, comp) - x.begin();
if(a < n && b >= 0){
res = max(res, maxVal(1, 0, n - 1, a, b) + tmp.second);
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> U >> V;
for(int i = 1; i <= N; ++i){
cin >> w[i] >> v[i];
}
cout << solve();
return 0;
}import sys
from bisect import bisect_left, bisect_right
def main():
data = sys.stdin.read().split()
N, U, V = int(data[0]), int(data[1]), int(data[2])
w = [0] * (N + 1)
v = [0] * (N + 1)
for i in range(1, N + 1):
w[i] = int(data[1 + 2 * i]); v[i] = int(data[2 + 2 * i])
# Vét cạn 1 nửa: trả về mọi cặp (tổng trọng lượng, tổng giá trị) có trọng lượng <= V
def gen(lo, hi):
res = [(0, 0)]
for i in range(lo, hi + 1):
res += [(a + w[i], b + v[i]) for a, b in res if a + w[i] <= V]
return res
x = gen(1, N // 2)
y = gen(N // 2 + 1, N)
x.sort(key=lambda p: p[0]) # chỉ sắp theo trọng lượng (giống hàm comp)
keys = [p[0] for p in x]
n = len(x)
# Segment tree (dạng mảng, xây từ dưới lên) để lấy max giá trị trên đoạn [a, b]
size = 1
while size < n:
size *= 2
NEG = -1
st = [NEG] * (2 * size)
for i in range(n):
st[size + i] = x[i][1]
for i in range(size - 1, 0, -1):
st[i] = max(st[2 * i], st[2 * i + 1])
def maxVal(a, b):
res = NEG
a += size; b += size + 1
while a < b:
if a & 1:
res = max(res, st[a]); a += 1
if b & 1:
b -= 1; res = max(res, st[b])
a //= 2; b //= 2
return res
res = 0
for wt, val in y:
a = bisect_left(keys, U - wt)
b = bisect_right(keys, V - wt) - 1
if a < n and b >= 0 and a <= b:
res = max(res, maxVal(a, b) + val)
print(res)
main()Giải thích một số chỗ trong code ở trên:
const int maxN = 1 << 16;– dịch bit sang trái,x << nlà $x \cdot 2^n$, nên1 << 16chính là $2^{16}$; mảngstcó kích thước4 * maxN.if(a < n && b >= 0) res = max(res, maxVal(1, 0, n - 1, a, b) + tmp.second);– kiểm tra 2 biên hợp lệ rồi mới cập nhật: giá trị lớn nhất ăn được từ $a$ tới $b$ trongxcộng với giá trị ăn được ởy. (Nếu $a \gt b$ thìmaxValtrả vềLLONG_MINnên cũng không ảnh hưởng đếnres.)for(pll tmp : y)– vòng lặp for each,tmplần lượt bằng từng phần tử trongy.- Hàm
solve()làm tất cả các bước: xây 2 vectorx,y, sortx, build segment tree, rồi duyệtyđể cập nhậtres.
Đánh giá độ phức tạp: không gian $O(6 \cdot 2^{N/2})$ (2 vector cỡ $2^{N/2}$ và segment tree cỡ $4 \cdot 2^{N/2}$). Thời gian: tạo 2 vector $2 \cdot 2^{N/2}$, sort $2^{N/2} \cdot N/2$, build cây $4 \cdot 2^{N/2}$, vòng lặp hợp nhất $2^{N/2} \cdot 3 \cdot N/2$; tổng lại khoảng $(6 + 2N) \cdot 2^{N/2}$, với $N = 32$ là khoảng $4.6 \cdot 10^6$ phép tính, thừa sức dưới 1 giây nha (mình chạy thử bản C++ mất khoảng 0.03 giây, bản Python khoảng 0.3 giây).
Bỏ comp đi thì sao?
Một điều khá hay nữa là nếu anh em bỏ comp ở lower_bound và upper_bound đi thì nộp bài vẫn AC:
int a = lower_bound(x.begin(), x.end(), (pll){U - tmp.first, 0}) - x.begin();
int b = --upper_bound(x.begin(), x.end(), (pll){V - tmp.first, 0}) - x.begin();Vậy không lẽ mình lý giải cho các bạn sai? Hãy thử test case này:
7 138 138
31 29
11 19
21 15
3 6
35 28
37 1
1 198Bỏ comp đi thì kết quả sẽ ra 0 (mình đã chạy thử, đúng là ra 0), trong khi kết quả phải là 98, chính là khi ăn 6 món đầu tiên (tổng trọng lượng đúng bằng 138). Còn có comp thì ra đúng 98. Test trên trang web không có test kiểu đó nên nộp mới AC nha.
Vậy để làm được bài này thì ta không chỉ phải biết kĩ thuật meet in the middle, mà còn phải nắm rõ segment tree, thậm chí phải hiểu rõ cách hoạt động của upper_bound và lower_bound nữa.
Try() cải tiến ở cách 1 bị dán nhầm dòng gọi đệ quy của phiên bản meet in the middle (Try(i + 1, des, ..., res)), mình đã sửa lại cho đúng ở trên. Bản Python cách 2 là mình viết thêm cùng ý tưởng (dùng bisect thay cho lower_bound/upper_bound trên mảng trọng lượng đã sắp xếp, nên tự nhiên chỉ so sánh theo trọng lượng). Tất cả các bản đã được kiểm tra với 300 bộ test ngẫu nhiên so với cách vét cạn.
Nhận xét
Đăng nhận xét