Trạm xăng vòng tròn

Buổi 12 — Greedy Algorithm greedy Implementation
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Trên một con đường khép kín hình tròn có $N$ trạm xăng được đánh số từ $0$ đến $N-1$ theo chiều kim đồng hồ. Tại trạm thứ $i$, xe có thể đổ thêm $g_i$ lít xăng, và để đi từ trạm $i$ đến trạm $(i+1) \bmod N$ cần tiêu tốn $c_i$ lít xăng. Ban đầu bình xăng của xe trống rỗng (dung tích bình xăng là vô hạn). Hãy tìm chỉ số trạm xuất phát nhỏ nhất sao cho xe có thể đi hết một vòng và quay lại trạm xuất phát, hoặc in ra -1 nếu không thể.

Dữ liệu vào
  • Dòng đầu tiên 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

Một số nguyên duy nhất là chỉ số trạm xuất phát nhỏ nhất (tính từ $0$), hoặc -1 nếu không tồn tại.

Ví dụ
Input Output
5\n1 2 3 4 5\n3 4 5 1 2 3
3\n2 3 4\n3 4 3 -1
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le g_i, c_i \le 10^6$
Draft saved