Đổ xăng ít lần nhất

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

Một chiếc xe xuất phát từ vị trí $0$ để đi đến đích ở vị trí $D$. Ban đầu xe có $F$ lít xăng (mỗi lít xăng đi được $1$ đơn vị khoảng cách, dung tích bình xăng là vô hạn). Dọc đường có $N$ trạm xăng, trạm thứ $i$ ở vị trí $p_i$ ($0 < p_i < D$) và có sẵn $f_i$ lít xăng. Khi đi qua một trạm xăng, xe có thể dừng lại để đổ toàn bộ $f_i$ lít xăng ở trạm đó. Hãy tìm số lần dừng đổ xăng ít nhất để xe đi tới đích $D$, hoặc in ra -1 nếu không thể tới đích.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, D, F$.
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p_i$ và $f_i$ (được cho theo thứ tự bất kỳ).
Dữ liệu ra

Một số nguyên duy nhất là số lần đổ xăng ít nhất, hoặc -1 nếu không thể tới đích.

Ví dụ
Input Output
4 100 10\n10 60\n20 30\n30 30\n60 40 2
1 100 10\n10 10 -1
Giới hạn
  • $0 \le N \le 10^5$
  • $1 \le D \le 10^9$, $0 \le F \le 10^9$
  • $0 < p_i < D$, $1 \le f_i \le 10^9$
Draft saved