Đối với bài toán này, ta không thể áp dụng binary search một cách đơn thuần được, vì mảng có chứa
số âm nên prefix sum sẽ không đơn điệu.
Theo yêu cầu đề bài, ta có:
$$pref[j]-pref[i-1] \le S$$
$$\iff pref[i-1] \ge pref[j]-S$$
Lúc này với mọi chỉ số $i$ thoả mãn, ta sẽ lấy chỉ số $i$ nhỏ nhất thoả mãn đồng thời $pref[i-1]$
phải đủ lớn để thoả $pref[i-1] \ge pref[j]-S$.
Nhận thấy rằng, nếu có hai chỉ số $i_1 < i_2$ và $pref[i_1] \ge pref[i_2]$, thì ta sẽ luôn luôn
chọn chỉ số $i_1$ vì $i_1$ nhỏ hơn, đồng thời vẫn đủ lớn để thoả điều kiện. Đơn giản là vì nếu giá
trị cực đại của $pref[i_1]$ không thoả mãn $pref[i_1] \ge pref[j]-S$, thì sẽ không có bất cứ giá
trị nào mà bé hơn $pref[i_1]$ thoả mãn được cả.
Từ quan sát trên, gọi $candidate[]$ là danh sách gồm các giá trị $pref[i]$ có thể thoả mãn.
Ban đầu, $candidate[0]=0$. Và với mỗi chỉ số $0 < i \le n$, ta sẽ đẩy $i$ vào danh sách nếu
$pref[i]$ lớn hơn giá trị $pref[j]$ cực đại trong $candidate$. Từ đây $candidate[]$ chỉ gồm các giá
trị $pref[j]$ tăng dần. Lúc này ta có thể áp dụng binary search để tìm $pref[i-1]$ nhỏ nhất thoả mãn
$pref[i-1] \ge pref[j] - S$
Độ phức tạp: $O(n\log(n))$
menkh
Created at
15 likes