POJ2431_Expedition_KEY

题目传送门

由题目可得,在一条路上有N个加油站,在距离终点a[i](细节)的位置上,你需要通过长度为L的路,油箱的容量是无限的,但是初始只有P点油,经过每个加油站时可以选择加b[i]的油,问最少加油几次可以到达终点。

可以看出经过每一个加油站时可以有两个选择:加油或不加油,但过去了就不能回来

假如我们就要没油了,我们是不是这样想:我当时应该在XX加油站加油才对。

所以,我们假设我们可以时空穿梭,回到经过XX加油站的时候,立即加油。

开一个堆记录经过的、未加油的加油站。

在即将没油时从堆里拿出油多的加油站加油,直到又有油可以到达下一个加油站。

这里有一个细节,要再设置一个在终点的、油量为0的加油站。

code:

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
using namespace std;
inline char getch(){
static char fl[],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
}
inline int read(){
char c;
while(!isdigit(c=getch()));int x=c-'';
while(isdigit(c=getch()))x=x*+c-'';
return x;
}
int L,P,i,now,ans;
struct node{
int x,y;
}a[];
inline int cmp(node x,node y){return x.x<y.x;}
int main(){
int N;
while(~scanf("%d",&N)){
for(i=;i<=N;i++)a[i].x=read(),a[i].y=read();
L=read(),P=read();
for(i=;i<=N;i++)a[i].x=L-a[i].x;
a[++N].x=L;priority_queue<int>w;
sort(a+,a+N+,cmp);
for(i=;i<=N;i++){
int cost=a[i].x-now;
while(P<cost){
if(w.empty()){puts("-1");return ;}
P+=w.top(),w.pop(),ans++;
}
w.push(a[i].y);
now=a[i].x,P-=cost;
}
printf("%d\n",ans);
}
}
上一篇:*(ptr++) += 123


下一篇:Android 常用的adb命令