题目大意:卡车每走一公里就消耗一单位的汽油,初始时给你p单位油,你要到达l距离的终点。其中路上有n个补给点可以加油,并且油箱容量无限大,问你最少可以停车几次。
思路:因为油箱无限大,所以我们可以这么认为,我们路过一个加油站之后,我们在之后的路上随时可以选择加那个加油站的油,而且肯定是一次加完B_i,所以我们从汽车初始状态开始开,到没油了,看看路上路过有加油站没,选路过过油最多的,加上,继续这样。最后加油次数一定是最少的
#include#include #include #include using namespace std;const int maxn=10005;struct node{ int d,f;};node a[maxn];bool cmp(node x,node y){ return x.d>y.d;}int main(){ int n,l,p; while(scanf("%d",&n)!=EOF) { priority_queue q; for(int i=0;i 0 && !q.empty()) { ++ans; int temp=q.top(); q.pop(); l-=temp; while(index