P9833 [USACO05OPEN] Expedition G 题解
[USACO05OPEN]Expedition G（题目传送门）
详细思路
贪心的模拟
首先审题，我们可以很容易得知车在它一次性耗完 初始油量 这段路程中经过的加油站里才能停下来加油 (每个加油站只能加一次油) 。
此时此刻，作为一个贪心的人我们不免贪心了起来 —— 既然要加油了，那为什么不去加那个能加 最多油 的加油站呢 (反正油是免费的) 。
既然都要去加最大油了，我们就可以去开一个 优先队列 去存一下它能加的最大油呢。
在加上油以后，我们只需要继续耗完这些油去重复上方的加油操作 OK 了。
如果他把它油箱里的油和路过的能加油的加油站用完了，但是到达不了下一个加油站或城市，那就 over 了。
于是乎，基于此等方法的思想便诞生了。
粗略思路
-
从初始开始，每一次都将油箱里边的油耗完，
然后进行时光倒流大法，回头再去一个加油站去加最大的油； -
如果某个加油站在它每次耗完油经过的这段路之间，将这个加油站放入优先队列里边，加一次油后
sum++； -
输出 -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);
}