自动搬运

查看原文

来自洛谷，原作者为

	Glass_S 我们都是平凡人，我们都不甘于平凡

搬运于2025-08-24 22:52:14，当前版本为作者最后更新于2023-11-11 12:09:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[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);
}