【51nod 1288】汽油补给

时间:2022-04-28 16:06:28

Description

有(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。

Input

第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)。

Output

输出走完整个旅程的最小花费,如果无法从起点到达终点输出-1。

Input示例

3 15
10 2
9 1
8 3

Output示例

41
 #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{long long d,p;}a[];
long long ans,n,T,d,p,st=,ed=,cnt;
long long read()
{
long long x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();T=read();
for(int i=;i<=n;i++)
{
d=read();p=read();cnt=;
if(d>T){printf("-1");return ;}
for(int i=st;i<ed;i++)
{
if(a[i].p<p)cnt+=a[i].d;
else ed=i;
}
if(cnt<T)a[ed].p=p,a[ed].d=T-cnt,ed++;
while(st<ed)
{
if(a[st].d<=d)ans+=a[st].d*a[st].p,d-=a[st].d,st++;
else ans+=d*a[st].p,a[st].d-=d,d=;
if(d<=)break;
}
}
printf("%lld",ans);
return ;
}