自动搬运

查看原文

来自洛谷，原作者为

	Alarm5854 Stop Smoking!

搬运于2025-08-24 22:30:17，当前版本为作者最后更新于2021-04-09 21:02:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题目看上去好像直接贪心就可以了，但是，其实在某些情况下，是可以走回头路的，所以就不能直接贪心求解了。

那么，怎么做呢？有一条显而易见的性质，就是不管是否走回头路，一定是一口气走到一个比这个点油价低的地方或走到终点，那么令终点有一个虚拟的加油站，油价为 $0$，这样就可以把终点和加油站一起进行处理了。

同时，也一定是恰好走到这个方向上离它最近的加油站，这个也非常容易证明。

根据这条性质，就能想到图论中的最短路——对于所有点，找左右两边各一个离它最近的点，其中这两个点的油价都低于该点的油价，往这两个点连边，长度为从这个点正好到达另一个点的耗费，如果没有，就不连。最多连 $2n$ 条边，可以用单调栈做到 $O(n)$ 。由于建成的图是有向无环图，所以只需用拓扑排序即可。

思路是这样的，然而有些细节需要注意：起始点所在的加油站必须要保证入度为 $0$，即遇到起始点就不让它进栈。在拓扑排序的时候，必须使所有入度为 $0$ 的点全部进队列，而不仅仅为起始点，否则 $0$ 分，原因就是一些无关的点也可能会往必要的点连边，使得这些必要的点入度永远不会减为 $0$，导致出错。

这样做总时间复杂度为 $O(n\log n)$，瓶颈在于排序（输入的坐标不保证有序）。

代码如下：

#include<ctime>
#include<queue>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e5+7;
ll read(){
	char c;
	ll x=0,f=1;
	while(!isdigit(c=getchar()))
		f-=2*(c=='-');
	while(isdigit(c)){
		x=x*10+f*(c-48);
		c=getchar();
	}
	return x;
}
struct pos{
	ll x,c;
	pos(ll a=0,ll b=0){
		x=a;
		c=b;
	}
	friend bool operator <(pos a,pos b){
		return a.x<b.x;
	}
};
struct edge{
	ll to,val,nxt;
	edge(ll a=0,ll b=0,ll c=0){
		to=a;
		val=b;
		nxt=c;
	}
};
pos p[N];
edge e[N];
ll top,st[N];
ll tot,head[N];
ll n,s,t,x,c,sx,tx,in[N],f[N];
void add(ll u,ll v,ll w){
	++in[v];
	e[++tot]=edge(v,w,head[u]);
	head[u]=tot;
}
void topo(){
	queue<ll>q;
	for(ll i=1;i<=n;++i){
		if(!in[i])
			q.push(i);
	}
	for(ll i=1;i<=n;++i)
		f[i]=5e18;//最大值可能会达到2e18
	f[sx]=0;//只有起始点的f值为0，其他均为正无穷
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		for(ll i=head[u];i;i=e[i].nxt){
			ll v=e[i].to;
			ll w=e[i].val;
			if(f[v]>f[u]+w)
				f[v]=f[u]+w;
			if(!--in[v])
				q.push(v);
		}
	}
}
int main(){
	n=read();
	s=read();
	t=read();
	for(ll i=1;i<=n;++i){
		c=read();
		x=read();
		p[i]=pos(x,c);
	}
	++n;
	p[n]=pos(t);
	sort(p+1,p+n+1);
	for(ll i=1;i<=n;++i){
		if(p[i].x==s)
			sx=i;
		if(p[i].x==t&&!p[i].c)
			tx=i;
	}
	for(ll i=1;i<=n;++i){
		while(top&&p[st[top]].c>=p[i].c){
			st[top]=0;
			--top;
		}
		if(top)
			add(i,st[top],(p[i].x-p[st[top]].x)*p[i].c);
		if(i^sx){//如果不为起始点，那么就使它进栈
			++top;
			st[top]=i;
		}
	}
	while(top){
		st[top]=0;
		--top;
	}
	for(ll i=n;i;--i){
		while(top&&p[st[top]].c>=p[i].c){
			st[top]=0;
			--top;
		}
		if(top)
			add(i,st[top],(p[st[top]].x-p[i].x)*p[i].c);
		if(i^sx){
			++top;
			st[top]=i;
		}
	}
	topo();
	printf("%lld",f[tx]);
	return 0;
}