「Test」走夜路

题意：一条路，$0$ 为起点 $n$ 为终点，每个点都有一个充电站，共 $n+1$ 个。Jim 有一个电量上限为 $t$ 的手电筒，一开始电筒没有电，Jim 每走一个单位距离消耗一单位点亮，依次给出每个充电站到下一个充电站的距离 $d _i$ 和这个充电站每冲一个单位电量的花费 $p$，现在问你走完这段路的最小花费。

一道贪心题。很明显在低价充电站多充电比高价充电站更优。对于每一个充电站 $i$，我们找到在他之后第一个电价小于当前站的充电站设为 $nxt _i$，这可以用单调栈求出(若没有满足条件的电站就把 $nxt _i$ 设为 $n+1$)。然后统计答案，如果当前拥有的电能够到达 $nxt _i$，就直接到达即可，否则就冲到刚好能够到达 $nxt _i$ 的电。如果 $nxt _i =n+1$，即不存在后面的电站电价更低，就直接充满即可，因为后面充电花费更高。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=500010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,t,d[maxn],p[maxn],nxt[maxn];
long long dis[maxn],now,ans,stack[maxn],top;
int main()
{
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&d[i],&p[i]);
		dis[i+1]=dis[i]+d[i];
	}
	for(int i=n;i>=1;i--)
	{
		while(top>0&&p[stack[top]]>=p[i])
			top--;
		nxt[i]=stack[top];
		stack[++top]=i;
		if(!nxt[i])
			nxt[i]=n+1;
	}
	for(int i=1;i<=n;i++)
	{
		now-=d[i-1];
		if(now<0)
		{
			printf("-1");
			return 0;
		}
		long long q=min(dis[nxt[i]]-dis[i],(long long)t);
		if(now<q)
		{
			ans+=p[i]*(q-now);
			now=q;
		}
	}
	printf("%lld",ans);
	return 0;
}