51nod 1288 汽油补给 贪心+单调栈

本文主要是介绍51nod 1288 汽油补给 贪心+单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1288 汽油补给

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 80 分
6.  
7. 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，当前城市为x，那么从x到y+1中间的道路消耗的油都应该尽量在x加。显然，对于每个城市的y是可以用O(n)的时间用单调栈处理出来的，那么剩下枚举也是O(n)了。

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

#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;
}

 

这篇关于51nod 1288 汽油补给 贪心+单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---