1288 汽油补给

1.0 秒

131,072.0 KB

80 分

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

例如D = {10, 9, 8}, P = {2, 1, 3}，T = 15，最小花费为41，在0加上10个单位的汽油，在1加满15个单位的汽油，在2加2个单位的汽油，走到终点时恰好用完所有汽油，花费为10 2 + 15 1 + 2 * 3 = 41。

收起

输入
第1行：2个数N, T中间用空格分隔，N + 1为城市的数量，T为油箱的容量(2 <= N <= 100000, 1 <= T <= 10^9)。
第2至N + 1行：每行2个数D[i], P[i]，中间用空格分隔，分别表示到下一个城市的距离和当地的油价（1 <= D[i], P[i] <= 1000000)。
输出
输出走完整个旅程的最小花费，如果无法从起点到达终点输出-1。
输入样例
3 15
10 2
9 1
8 3
输出样例
41

分析：

是一个典型的贪心算法，实际上可以枚举当前的城市，然后去计算当前的城市的油价一直到后面哪个城市都是最小的，设这个数为y（r[i])-1，当前城市为x，那么从x到y+1中间的道路消耗的油都应该尽量在x加。显然，对于每个城市的y是可以用O(n)的时间用单调栈处理出来的，那么剩下枚举也是O(n)了。

接下类就好办了，对于当前位置i，尽量加到max(跑完[i,r[i]-1]的这一段区间见，邮箱容量）。

另一种写法：

一个比较好写的思路大概是，一直保持油箱是满的，同时油箱看作分了很多块儿，每块的油价格是不一样的。行驶过程中，先消耗便宜的油，每到一个加油站，可以把油箱中比当前油价贵的油换掉，换成当前的价格。这样也是利用一个单调栈，时间复杂度O(n)。

IA=lambda:map(int,input().split())

n,m=IA()
d=[0 for i in range(0,n+1)]
p=[0 for i in range(0,n+1)]
r=[0 for i in range(0,n+1)]
summ=[0 for i in range(0,n+1)]

for i in range(1,n+1):
    
    d[i],p[i]=IA()
    summ[i]=summ[i-1]+d[i]


sta=[0 for i in range(0,n+1)]
tt=0

for i in range(n,0,-1):
    
    while tt!=0 and p[sta[tt]]>p[i]:
        tt-=1
    if tt==0:
        r[i]=n+1
    else:
        r[i]=sta[tt]
    tt+=1
    sta[tt]=i
    
ans=0 
now=0

for i in range(1,n+1):
    if d[i]>m:
        ans=-1
        break
    dd=summ[r[i]-1]-summ[i-1]
    cha=now-dd
    if cha>=0:
        now-=d[i]
        continue
    if m<dd:
        ans+=(m-now)*p[i]
        now=m
    else:
        ans+=(dd-now)*p[i]
        now=dd
    now-=d[i]

print(ans)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500005;
LL n,t;
LL d[N],p[N],sum[N];
int r[N];
stack<LL> s;
int main()
{
	
	scanf("%lld%lld",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&d[i],&p[i]);
		sum[i]=sum[i-1]+d[i];
	}
	
	
	for(int i=n;i>=1;i--)
	{
		if(d[i]>t)
		{
			cout<<-1<<endl;
			return 0;
		}
		while(!s.empty()&&p[s.top()]>=p[i])
			s.pop();
	    if(s.empty()) r[i]=n+1;
	    else r[i]=s.top();
	    s.push(i);
	}
	
	LL now=0;
	LL ans=0;
	for(int i=1;i<=n;i++)
	{
		LL maxx=sum[r[i]-1]-sum[i-1];
	    LL cha=min(t,maxx)-now;
		// cout<<"S"<<r[i]<<" "<<cha<<" "<<now<<" "<<endl;;
		if(cha<=0)
		{
			now-=d[i];
			continue;
		} 
		now+=cha;
		now-=d[i];
		ans+=p[i]*cha;
		//cout<<w<<" "<<ans<<endl;
		
	}
	printf("%lld\n",ans);
	
	
	
	return 0;
}