Hành trình qua các trạm xăng
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Có $N$ trạm xăng nằm trên một vòng tròn, đánh số từ $0$ đến $N - 1$. Tại trạm $i$ bạn được đổ $G_i$ lít xăng, và để đi từ trạm $i$ tới trạm $(i + 1) \bmod N$ cần tốn $C_i$ lít xăng. Ban đầu bình xăng rỗng (dung tích bình vô hạn). Hãy tìm chỉ số trạm xuất phát nhỏ nhất sao cho bạn có thể đi hết một vòng tròn. Nếu không thể, in ra -1.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $G_0, G_1, \dots, G_{N-1}$. Dòng thứ ba chứa $N$ số nguyên $C_0, C_1, \dots, C_{N-1}$.
Dữ liệu ra
In ra chỉ số trạm xuất phát nhỏ nhất (từ $0$ đến $N-1$), hoặc -1 nếu không có.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 3 4 5 3 4 5 1 2 |
3 |
| 3 2 3 4 3 4 3 |
-1 |
Giới hạn
- $1 \le N \le 10^5$.
- $0 \le G_i, C_i \le 10^9$.
Community Discussion