Hướng dẫn giải của Xếp gạch
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
An được chọn: mỗi lượt có thể dùng b_i để xếp thêm gạch vào chồng j, với điều kiện các chồng j..n chưa từng được xếp thêm. Tìm số điểm lớn nhất, tức max của min(số gạch).
Sub 1: Nhị phân + kiểm tra DP, ~n, m \le 100~ ~O(\log V \cdot n \cdot m)~
Nhị phân trên điểm X; kiểm tra bằng DP tập chỉ số lượt cuối cùng dùng được. Chạy riêng subtask này đạt 14/20 test.
Sub 2: Nhị phân + tham lam, ~n, m \le 10^5~ ~O(\log V \cdot (n+m))~
Chồng thiếu d = X - a_j cần lượt đầu tiên (theo thứ tự) có b >= d; tham lam chọn lượt sớm nhất là đúng. Chạy riêng subtask này đạt 20/20 test.
Chương trình hoàn chỉnh
Nếu n, m <= 100 dùng sub 1, ngược lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<ll> a, b;
// Chon X co dat duoc khong (tham lam, dung khi n > 100 hoac m > 100):
// moi chong can them d = X - a[j] > 0 phai dung mot luot co b >= d, cac luot dung tang dan theo thu tu chong
bool feasibleGreedy(ll X) {
int p = 0; // luot tiep theo co the dung (0-based)
for (int j = 0; j < n; j++) {
if (a[j] >= X) continue;
ll d = X - a[j];
while (p < m && b[p] < d) p++;
if (p == m) return false;
p++; // luot b[p] da dung cho chong j
}
return true;
}
// Kiem tra bang quy hoach dong (dung khi n, m <= 100): tap cac "luot cuoi cung da dung" co the
bool feasibleDP(ll X) {
vector<char> S(m + 1, 0); // S[i]: co the da dung luot i (1-based), S[0]: chua dung luot nao
S[0] = 1;
for (int j = 0; j < n; j++) {
if (a[j] >= X) continue;
ll d = X - a[j];
vector<char> T(m + 1, 0);
bool prefix = false; // co i < ip voi S[i] = 1 hay khong
for (int ip = 1; ip <= m; ip++) {
prefix = prefix || S[ip - 1];
if (prefix && b[ip - 1] >= d) T[ip] = 1;
}
S = T;
}
for (int i = 0; i <= m; i++) if (S[i]) return true;
return false;
}
// Sub 1: tim kiem nhi phan + kiem tra DP, dung khi n, m <= 100
void sub1() {
ll lo = *min_element(a.begin(), a.end()); // lo luon dat duoc
ll hi = *max_element(a.begin(), a.end()) + *max_element(b.begin(), b.end()) + 1; // hi chac chan khong dat
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
if (feasibleDP(mid)) lo = mid;
else hi = mid;
}
cout << lo << "\n";
}
// Sub 2: tim kiem nhi phan + kiem tra tham lam, dung cho n, m lon
void sub2() {
ll lo = *min_element(a.begin(), a.end());
ll hi = *max_element(a.begin(), a.end()) + *max_element(b.begin(), b.end()) + 1;
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
if (feasibleGreedy(mid)) lo = mid;
else hi = mid;
}
cout << lo << "\n";
}
int main() {
freopen("B3.INP", "r", stdin);
freopen("B3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
a.resize(n);
b.resize(m);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
if (n <= 100 && m <= 100) sub1();
else sub2();
return 0;
}
Bình luận