注意题目给的是到终点的距离,需要转成到起点的距离,还有就是将终点也看成是加油站,这样写起来方便很多,不必要单独考虑最后一个加油站不在终点以后的情况
#include
#include
#include
#include
#include
using namespace std; int N,P,L; pair
d[10100]; bool cmp(pair
a, pair
b) { return a.first > b.first; } void solve() { priority_queue
que; sort(d,d+N,cmp); d[N].first = L, d[N++].second = 0; int ans = 0, pos = 0, tank = P; for(int i = 0; i < N; i++) { if(i != N - 1) d[i].first = L - d[i].first; int dis = d[i].first - pos; while(tank < dis) { if(!que.empty()) { tank += que.top(); que.pop(); ans++; } else { cout<<"-1"<
>N) { for(int i = 0; i < N; i++) { cin>>d[i].first>>d[i].second; } cin>>L>>P; solve(); } return 0; }