Hướng dẫn giải của [VTT Q4 Contest 09] Bài 2: Hoa tặng mẹ [FLOWERS]
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
Chọn đúng một nhánh lan và một bông hồng sao cho tổng giá lớn nhất mà không vượt quá ~S~. Giá đều không quá ~10^6~ nên có thể dùng bảng tra theo giá trị. Bài có nhiều đáp án đúng; chương trình dưới đây in đúng kiểu đáp án mẫu (nhánh lan rẻ nhất trong các phương án tối ưu, chỉ số nhỏ nhất; bông hồng có chỉ số lớn nhất).
Sub 1: Vét cạn — ~O(n \cdot m)~, dùng khi ~n, m \le 1000~
Thử mọi cặp ~(i, j)~, giữ cặp có tổng lớn nhất không vượt quá ~S~. Nếu chỉ nộp sub này: đúng 14/20 test (6 test lớn bị quá thời gian).
Sub 2: Bảng tra theo giá — ~O(n + m + \max b)~
Lập mảng f[v] là chỉ số của bông hồng có giá lớn nhất không vượt quá ~v~ (tính dần ~v = 1, 2, \dots, 10^6~: nếu có bông hồng giá đúng ~v~ thì lấy nó, không thì lấy f[v-1]). Với mỗi nhánh lan giá ~a_i~, bông hồng tốt nhất là f[S - a_i] (cắt ~S - a_i~ tại ~10^6~; nếu ~S - a_i < 1~ thì bỏ qua). Lấy cặp tốt nhất qua mọi ~i~. Bẫy: ~S~ lên đến ~10^9~ nên phải chặn chỉ số mảng; tổng phải dùng long long cho an toàn; khi không có cách mua thì in 0 0. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; khi ~n, m \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long S;
vector<int> a, b;
// So sánh hai phương án: tổng lớn hơn thì tốt hơn; bằng nhau thì chọn nhánh lan
// rẻ hơn (trùng giá: chỉ số nhỏ hơn), bông hồng có chỉ số lớn hơn — khớp đáp án mẫu
bool better(long long t, int i, int j, long long best, int bi, int bj) {
if (t != best) return t > best;
if (bi == 0) return true;
if (a[i] != a[bi]) return a[i] < a[bi];
if (i != bi) return i < bi;
return j > bj;
}
// Sub 1: thử mọi cặp (i, j) — O(n*m)
void sub1() {
long long best = 0; int bi = 0, bj = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
long long t = (long long)a[i] + b[j];
if (t <= S && better(t, i, j, best, bi, bj)) { best = t; bi = i; bj = j; }
}
if (best == 0) cout << "0 0\n";
else cout << best << " " << bi << " " << bj << "\n";
}
// Sub 2: giá <= 10^6 nên lập bảng: với mỗi giá trị v, f[v] = chỉ số bông hồng
// có giá lớn nhất không vượt quá v. Duyệt từng nhánh lan, tra bảng — O(n+m+maxA)
void sub2() {
const int MX = 1000000;
vector<int> f(MX + 1, 0), pos(MX + 1, 0);
for (int j = 1; j <= m; j++) pos[b[j]] = j; // chỉ số lớn nhất ứng với mỗi giá (khớp đáp án mẫu)
for (int v = 1; v <= MX; v++) f[v] = pos[v] ? pos[v] : f[v - 1];
long long best = 0; int bi = 0, bj = 0;
for (int i = 1; i <= n; i++) {
long long rest = S - a[i];
if (rest < 1) continue;
int j = f[min<long long>(rest, MX)];
if (j == 0) continue;
long long t = (long long)a[i] + b[j];
if (better(t, i, j, best, bi, bj)) { best = t; bi = i; bj = j; }
}
if (best == 0) cout << "0 0\n";
else cout << best << " " << bi << " " << bj << "\n";
}
int main() {
freopen("FLOWERS.INP", "r", stdin);
freopen("FLOWERS.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> S;
a.assign(n + 1, 0); b.assign(m + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int j = 1; j <= m; j++) cin >> b[j];
if (n <= 1000 && m <= 1000) sub1();
else sub2();
}
Bình luận