题目传送门
【题目大意】
卡车要去往距离起点为$L$的城镇，出发时有$P$升汽油，每经过一单位距离消耗一升汽油，从起点到城镇的路上有$n$个加油站，油箱可以容纳无穷多的油，求最少要在多少个加油站加油才能顺利到达城镇。
【思路分析】
用一个单调队列存储加油站信息，按照汽油从大到小排序，每经过一个加油站就把它加入队列，如果当前油箱里的汽油不够到下一个加油站了，那就取出队头，更新各项信息，相当于在那个加油站加了油，细节见代码。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define g() getchar() 8 #define rg register 9 #define go(i,a,b) for(rg int i=a;i<=b;i++) 10 #define back(i,a,b) for(rg int i=a;i>=b;i--) 11 #define db double 12 #define ll long long 13 #define il inline 14 #define pf printf 15 using namespace std; 16 int fr(){ 17 int w=0,q=1; 18 char ch=g(); 19 while(ch<'0'||ch>'9'){ 20 if(ch=='-') q=-1; 21 ch=g(); 22 } 23 while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g(); 24 return w*q; 25 } 26 const int N=10002; 27 int n,L,P; 28 priority_queue<int> q; 29 struct stop{ 30 int dis,sum; 31 }a[N]; 32 il bool cmp(stop x,stop y){ 33 return x.dis<y.dis; 34 } 35 int main(){ 36 //freopen("","r",stdin); 37 //freopen("","w",stdout); 38 n=fr(); 39 go(i,1,n) a[i].dis=fr(),a[i].sum=fr(); 40 L=fr();P=fr(); 41 go(i,1,n) a[i].dis=L-a[i].dis; 42 //把题目中加油站到城镇的距离转化为加油站到起点的距离 43 sort(a+1,a+1+n,cmp);//按照距离排序 44 a[++n].dis=L;a[n].sum=0;//把终点看作一个距离为L,汽油量为0的加油站 45 rg int now=P,pos=0,ans=0; 46 //now记录油箱里剩余的汽油量,pos记录上一个加油站的位置,ans记录加油次数 47 go(i,1,n){ 48 rg int d=a[i].dis-pos; 49 while(now<d){ 50 if(q.empty()) {pf("-1\n");return 0;}//如果队列为空则不可能到达 51 ans++; 52 now+=q.top();q.pop();//加油 53 } 54 now-=d;q.push(a[i].sum);pos=a[i].dis; 55 } 56 pf("%d\n",ans); 57 return 0; 58 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11388562.html
