Giả sử ta chỉ xét chiều xe di chuyển là theo chiều kim đồng hồ (aka. từ $i \rightarrow i+1$ và $n \rightarrow 1$). Trường hợp theo chiều ngược kim đồng hồ ta làm tương tự nhưng ngược lại.
Gọi $f$ là lượng xăng có được khi ta di chuyển tới trạm ở vị trí $i$. Lúc này, ta sẽ được nạp $p_i$ lít xăng, và nếu di chuyển tới trạm $i+1$ thì lại mất đi $r_i$ lít xăng.
Do vậy, khi đi từ trạm $i$ tới $i+1$ ta sẽ có lượng xăng mới là $f+p_i-r_i$.
<hr>
#### Vậy câu hỏi đặt ra là: khi nào ta không thể đi tiếp?
Câu trả lời rất đơn giản: đó là khi $f < 0$, hay tồn tại một vị trí nào đó trên quãng đường di chuyển mà lượng xăng về âm. Lúc đó chắc chắn ta không thể đi tiếp được do đã hết xăng rồi.
<hr>
Trước hết, ta gấp đôi mảng lên để tiện lợi cho việc xử lý xoay vòng.
Lúc này, việc xuất phát tại $i$ và đi hết một vòng về lại $i$ tương đương di chuyển từ $i$ tới $i+n$ trên mảng, nghĩa là ta phải nạp nhiên liệu ở các trạm $i, i+1,..., i+n-1$.
Ta đưa về bài toán: trên mọi đoạn con $[i; i+n-1]$, kiểm tra xem liệu có tồn tại một vị trí sao cho $f<0$. Nếu tồn tại nghĩa là không thể đi được. Ngược lại, nếu mọi $f$ đều $\ge 0$ thì ta có thể đi được. Biết rằng, mỗi lần nạp nhiên liệu thì $f:=f+d_i-r_i$.
Gọi $\text{pre}[i]$ là lượng xăng khi **tới** $i$ mà xuất phát tại vị trí $1$, nghĩa là $\text{pre}[i] = \text{pre}[i - 1] + (p_{i-1} - r_{i-1})$.
Lưu ý: ở đây ta xét khi tới $i$, nghĩa là ta chưa hề nạp xăng tại $i$ cũng như di chuyển sang $i+1$, mà là nạp xăng tại vị trí $i-1$ và di chuyển tới $i$. Do vậy ta mới xét giá trị $p_{i-1} - r_{i-1}$.
Dễ thấy $\text{pre}$ chính là mảng cộng dồn. Do đó, ta di chuyển từ $i$ tới $j$ thì lượng xăng khi tới $j$ là $\text{pre}[j] - \text{pre}[i]$.
Vậy bài toán sẽ là kiểm tra xem có tồn tại $j$ sao cho $i+1 \le j \le i + n$ và $\text{pre}[j] - \text{pre}[i] < 0$ hay không, nghĩa là lượng xăng dưới $0$ và không đi được.
Ta sẽ chọn $j$ sao cho $\text{pre}[j] - \text{pre}[i]$ nhỏ nhất. Mà $i$ cố định nên cần tìm $j$ thỏa $\text{pre}[j]$ là nhỏ nhất và nằm trong đoạn $[i+1; i+n]$. Lúc này ta có thể sử dụng *ctdl deque* để tịnh tiến min trên đoạn $i+1$ tới $i+n$ độ dài cố định là $n$. Nếu tìm được $\text{pre}[j] - \text{pre}[i]$ nhỏ nhất nhưng lại $\ge 0$ thì mọi giá trị khác nằm trong đoạn cũng sẽ $\ge 0$ do $\text{pre}[j]$ đã là nhỏ nhất.
Vậy nếu tìm được $j$ thỏa $\text{pre}[j]$ nhỏ nhất thì nếu $\text{pre}[j] - \text{pre}[i] \ge 0$ thì ta đi được `TAK`, còn không thì `NIE` (à đừng quên là chưa xong đâu vì còn phải xét ngược chiều kim đồng hồ nữa nha).
<hr>
### Giả code (C++)
**Lưu ý:** Lúc code do sơ ý nên mình đã làm "mất" một số đoạn code khiến code không chạy được, bạn hãy giúp mình sửa chữa lại nhé. Đoạn code bị mất được thay thế bằng "???".
Đây là code của mình:
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6;
int n, p[MAXN * 2 + 5], d[MAXN * 2 + 5], pre[MAXN * 2 + 5], suf[MAXN * 2 + 5];
bool res[MAXN + 5] = {};
void solve(){
deque<int> dq;
for(int i = 1; i <= n * 2; ++i){
if(!dq.empty() && i - dq.back() + 1 > n) dq.pop_back();
while(!dq.empty() && ???) dq.pop_front();
dq.push_front(i);
if(i >= n + 1){
res[i - n] |= pre[dq.back()] - ??? >= 0;
}
}
dq.clear();
for(int i = n * 2; i >= 1; --i){
???
}
for(int i = 1; i <= n; ++i){
cout << (res[i] ? "TAK" : "NIE") << '\n';
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> p[i] >> d[i];
???
}
for(int i = 1; i <= n * 2; ++i){
pre[i] = pre[i - 1] + (p[i - 1] - d[i - 1]);
}
for(int i = n * 2; i >= 1; --i){
suf[i] = suf[i + 1] + (p[i + 1] - d[i]);
}
solve();
return 0;
}
```
Lưu ý: có thể thấy là `suf` chính là `pre` nhưng phiên bản xét cho chiều ngược kim đồng hồ.
hungg_261
Created at
0 likes