Hướng dẫn giải của Hồ chứa nước
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.
Ở bài toán này, bạn được yêu cầu giải bài toán xuôi: cho lượng nước W, tính cột lớn nhất mà nước chảy đến.
Ta xét bài toán ngược lại: Nếu nước chỉ chảy đến cột lớn nhất là i, lượng nước tối đa W là bao nhiêu?
Ta ký hiệu bài toán xuôi là f: cho W, tính f(W) = cột lớn nhất.
Ký hiệu bài toán ngược là g: cho i, tính g(i) = W là lượng nước lớn nhất.
Việc tính bài toán xuôi (tính f) là khó, do miền giá trị của W có thể lên đến 10^15. Nhưng việc giải bài toán ngược (tính g) lại đơn giản hơn, do miền giá trị của i chỉ đến 10^5. Để tính g ta có thể quy hoạch động và tính trước toàn bộ hàm g với tất cả các giá trị của i.
Khi có mảng g, ta có thể dùng phương pháp chặt nhị phân để tính f.
Tính mảng g
Việc tính g gồm 2 bước:
Tính trước mảng left[u] là cột đứng trước và gần cột u nhất mà height[i] > height[u]. (Khởi tạo cột 0 có chiều cao rất lớn)
Tính g[u] là lượng nước tối đa nếu nước không tràn qua cột u.
Bước 1 đã được giải thích rất cụ thể trong bài viết: Tìm min-max trên đoạn tịnh tiến.
Với bước 2, từ hình vẽ, có thể thấy g(u) là tổng của:
- Lượng nước từ đầu đến cột left(u), chính là g(left(u))
- Thể tích nước từ sau cột left[u] đến cột u. Chú ý ta cần trừ đi thể tích các cột từ left(u) đến u: (position[i] - position[u]) * h[u] - tổng(các cột trong khoảng từ sau cột i đến u)
Chặt nhị phân
Để tính f(W), ban đầu ta biết f(W) nằm trong khoảng [0, N].
Xét cột mid = N/2.
Nếu g(mid) >= W, rõ ràng đến cột mid, ta có thể chứa được nhiều nước hơn, nên kết quả <= mid.
Ngược lại, kết quả > mid.
Như vậy, với 1 phép so sánh, ta biết được f(W) nằm trong [0, mid] hay [mid+1, N]: ta đã giảm đi được 2 lần khoảng cần tìm. Tiếp tục làm như vậy, ta sẽ tính được hàm f với độ phức tạp O(logN):
Pseudo code:
L = 0
R = N
res = N
while L <= R:
mid = (L + R) / 2
if g(mid) >= W:
res = mid
R = mid - 1
else:
L = mid + 1
Kết quả cuối cùng là res
Lời giải tham khảo
// Author: RR
// O(N), stack
#include <sstream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <queue>
#include <bitset>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i)
#define DEBUG(X) { cerr << #X << " = " << (X) << endl; }
#define PR(A, n) { cerr << #A << " = "; FOR(_, 1, n) cerr << A[_] << ' '; cerr << endl; }
#define PR0(A, n) { cerr << #A << " = "; REP(_, n) cerr << A[_] << ' '; cerr << endl; }
#define sqr(x) ((x) * (x))
#define ll long long
#define __builtin_popcount __builtin_popcountll
#define SZ(x) ((int)(x).size())
using namespace std;
double safe_sqrt(double x) { return sqrt(max((double)0.0, x)); }
int GI(ll& x) { return scanf("%lld", &x); }
const int MN = 100111;
#define left left____
int pos[MN], h[MN], st[MN], left[MN], top, sum[MN], water[MN];
#undef int
int main() {
#define int long long
ios::sync_with_stdio(0);
cin.tie(0);
cout << (fixed) << setprecision(9);
int ntest; GI(ntest);
FOR(test,1,ntest) {
int n; GI(n);
FOR(i,1,n) GI(pos[i]);
FOR(i,1,n) {
GI(h[i]);
sum[i] = sum[i-1] + h[i];
}
top = 0;
st[0] = 0;
FOR(i,1,n) {
while (top && h[st[top]] <= h[i]) --top;
left[i] = st[top];
st[++top] = i;
}
h[0] = 1000111000;
pos[0] = -1;
FOR(i,1,n) {
int u = left[i];
water[i] = water[u] + (pos[i] - pos[u]) * h[i] - (sum[i] - sum[u]);
}
int q; GI(q);
while (q--) {
int k; GI(k);
int l = 0, r = n, res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (water[mid] < k) {
res = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
printf("%lld\n", res);
}
}
}
Source: Bài B, ICPC Vietnam 2016
Bình luận