[PTNK - TS10 - 2025] Bài 2: EVTRIP
Xem dạng PDF
Gửi bài giải
Điểm:
20,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Một chiếc xe điện bắt đầu hành trình từ điểm 0 km với pin đầy, dung lượng pin tối đa là ~P_{max}~ đơn vị. Mỗi km di chuyển tiêu tốn 1 đơn vị pin.
Trên quãng đường có ~N~ trạm sạc. Trạm thứ ~i~ (với ~i=1, 2, \dots, N~) nằm ở vị trí ~D_i~ km tính từ điểm xuất phát và tại đó xe có thể sạc đầy pin (lên ~P_{max}~) ngay lập tức.
Xe không thể di chuyển nếu pin không đủ cho 1 km tiếp theo. Đích đến là thành phố ở vị trí ~D_{target}~ km.
Yêu cầu: Tìm số lần sạc ít nhất để xe có thể đi từ điểm 0 đến ~D_{target}~. Nếu không thể đến đích, ghi ra -1.
Input
- Dòng đầu tiên: ba số tự nhiên ~N, P_{max}, D_{target}~ (~0 \le N \le 1000, 1 \le P_{max} \le 10^9, 1 \le D_{target} \le 10^9~).
- ~N~ dòng tiếp theo: mỗi dòng chứa một số nguyên ~D_i~ (~1 \le D_i < D_{target}~).
Output
- Một số nguyên là số lần sạc ít nhất, hoặc -1 nếu không thể đến đích.
Sample Input 1
3 175 350
80
180
280
Sample Output 1
2
Bình luận
include<bits/stdc++.h>using namespace std;int main(){long long N,P,D;cin>>N>>P>>D;vector<long long>a(N);for(auto&i:a)cin>>i;a.push_back(D);sort(a.begin(),a.end());long long ans=0,last=0,pos=0;for(long long x:a){long long d=x-pos;if(d>P)return cout