[USACO05OPEN]Expedition G（题目传送门）

详细思路

贪心的模拟

首先审题，我们可以很容易得知车在它一次性耗完 初始油量 这段路程中经过的加油站里才能停下来加油 (每个加油站只能加一次油) 。

此时此刻，作为一个贪心的人我们不免贪心了起来 —— 既然要加油了，那为什么不去加那个能加 最多油 的加油站呢 (反正油是免费的) 。

既然都要去加最大油了，我们就可以去开一个 优先队列 去存一下它能加的最大油呢。

在加上油以后，我们只需要继续耗完这些油去重复上方的加油操作 OK 了。

如果他把它油箱里的油和路过的能加油的加油站用完了，但是到达不了下一个加油站或城市，那就 over 了。

于是乎，基于此等方法的思想便诞生了。

粗略思路

1. 从初始开始，每一次都将油箱里边的油耗完，然后进行时光倒流大法，回头再去一个加油站去加最大的油；

2. 如果某个加油站在它每次耗完油经过的这段路之间，将这个加油站放入优先队列里边，加一次油后 sum++；

3. 输出 -1 的操作：如果他把它手里的油和加油站用完了，但是到达不了下一个加油站或城市，那就永远到不了了。

my AC 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<algorithm>
#define lp (p*2)
#define rp (p*2+1)
#define mid ((l+r)/2)
#define int long long
#define N 10010
using namespace std;
int n,l,p,sum,tim=1;
int vis[N];
struct oil
{
	int local,hav;//local是加油站距城市的距离,hav就是它能提供的油量
}a[N];
priority_queue<int>q;//利用优先队列去存它的最大能加的油量 
bool cmpx(const oil a,const oil b)//定义sort让a[]从大到小排列 
{
	return a.local>b.local;
}
int re() 
{
	int x=0,p=1;
	char y=getchar();
	for(;y<'0'||y>'9';y=getchar())
	    if(y=='-')
	        p=-p;
	for(;y>='0'&&y<='9';y=getchar())
	    x=x*10+y-'0';
	return x*p;
}
void wr(int x) 
{
	if(x<0)
	    x=-x,putchar('-');
	if(x>9)
	    wr(x/10);
	putchar(x%10+'0');
}
signed main()
{
	n=re();
	for(int i=1;i<=n;i++)
	    a[i].local=re(),a[i].hav=re();
	l=re(),p=re();//l为到城市的距离，p为目前油量
	sort(a+1,a+n+1,cmpx);
	while(1)
	{
		l-=p;
		if(l<=0)//当到城市的距离小于等于0，结束循环 
		    break;
		    
		for(int i=tim;i<=n;i++)
		    if(a[i].local>=l&&a[i].local<=l+p)
		    	    q.push(a[i].hav);//只有他能到达的加油站，才能给他加油 
			else {
			    tim=i;//为了方便判断下边输出-1的情况，和优化一下此for循环 
				break;
			}	
		p=q.top();//优先队列第一个就是他最大能加的油量 
		q.pop();
		sum++;
		if(q.empty()&&a[tim].local<(l-p))//如果她走过的站已经没有再能给他加油的，并且他还到达不了下一个站 
		    wr(-1),exit(0);//输出-1且结束程序 
	}
	wr(sum);
}

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> Q;
struct node{int x, u;}a[11000];
bool cmp(node n1, node n2){ return n1.x < n2.x;}

int n, L, P;

bool pd()
{
    int np = P;
    for(int i = 2; i <= n; i++)
    {
        np -= (a[i].x - a[i-1].x);
        if(np < 0) return 0;
        np += a[i].u;
    }
    return 1;
}
int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].x, &a[i].u);

    scanf("%d%d", &L, &P);
    for(int i = 1; i <= n; i++)
        a[i].x = L - a[i].x;
    a[n+1].x = 0, a[n+1].u = 0;
    a[n+2].x = L, a[n+2].u = 0;
    n += 2;
    sort(a + 1, a + n + 1, cmp);
    
    if(pd() == 0){ printf("-1"); return 0; }
    
    int ans = 0, np = P;
    for(int i = 2; i <= n; i++)
    {
        np -= (a[i].x - a[i-1].x);
        while(np < 0)
        {
            np += Q.top();
            Q.pop();
            ans++;
        }
        Q.push(a[i].u);
    }
    printf("%d\n", ans);
    return 0;
}