[多校联考2019(Round 4 T2)][51nod 1288]汽油补给(ST表+单调栈)

[51nod 1288]汽油补给(ST表+单调栈)

题面

有（N+1）个城市，0是起点N是终点，开车从0 -> 1 - > 2...... -> N，车每走1个单位距离消耗1个单位的汽油，油箱的容量是T。给出每个城市到下一个城市的距离D，以及当地的油价P，求走完整个旅途最少的花费。如果无法从起点到达终点输出-1。

分析

贪心考虑，当我们到达一个城市x的时候，我们下一个到的城市应该是在x加满油的情况下，能到达的油价比x低的城市。如果每个加油城市之间的路都这样走，那么最后的价钱一定是最小的.

油价比x低的城市编号可以倒着维护一个单调栈预处理出来。但是有一种特殊情况，即加满油的情况下到不了油价比x低的城市。这种情况用ST表维护区间最小值，查询能到达的范围内油价最低的城市.

细节很多，见代码.

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 500000

#define maxlogn 25

using namespace std;

typedef long long ll;

int n,lim;

ll dist[maxn+5];

ll p[maxn+5];

struct sparse_table{

	int log2[maxn+5];

	int st[maxn+5][maxlogn+5];

	void ini(){

		log2[0]=-1;

		for(int i=1;i<=n;i++) log2[i]=log2[i>>1]+1;

		for(int i=1;i<=n;i++) st[i][0]=i;

		for(int j=1;(1<<j)<=n;j++){

			for(int i=1;i+(1<<j)-1<=n;i++){

				if(p[st[i][j-1]]<p[st[i+(1<<(j-1))][j-1]]) st[i][j]=st[i][j-1];

				else st[i][j]=st[i+(1<<(j-1))][j-1];

			}

		}

	}

	int query(int l,int r){

		int k=log2[r-l+1];

		if(p[st[l][k]]<p[st[r-(1<<k)+1][k]]) return st[l][k];

		else return st[r-(1<<k)+1][k];

	}

}T;

int top=0;

int nex[maxn+5];//后面油价比i低的城市

int s[maxn+5];

void calc_nex(){

	top=0;

	s[++top]=n+1;

	for(int i=n;i>=1;i--){

		while(p[i]<=p[s[top]]) top--;

		nex[i]=s[top];

		s[++top]=i;

	}

}

int main(){

//	freopen("1.in","r",stdin);

	int len;

	scanf("%d %d",&n,&lim);

	for(int i=1;i<=n;i++){

		scanf("%d",&len);

		dist[i+1]=dist[i]+len;

		scanf("%lld",&p[i]);

		if(len>lim){

			printf("-1\n");

			return 0;

		}

	}

	T.ini();

	calc_nex();

	int x=1,r=1;

	ll ans=0;

	ll vol=0;//当前油量

	while(x<=n){

		while(dist[r+1]-dist[x]<=lim) r++;

		if(nex[x]<=r){//加满油到nex[x]

			int y=nex[x];

			if(vol<dist[y]-dist[x]) ans+=p[x]*(dist[y]-dist[x]-vol);

			vol=0;

			x=nex[x];

		}else{//即使加满，油量也不够到达nex[x]

			int y=T.query(x+1,r);

			ans+=p[x]*(lim-vol);

			vol=lim-(dist[y]-dist[x]);

			x=y;

		}

	}

	printf("%lld\n",ans);

}