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
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 struct node{long long d,p;}a[100050]; 6 long long ans,n,T,d,p,st=1,ed=1,cnt; 7 long long read() 8 { 9 long long x=0,f=1;char c=getchar(); 10 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 11 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 12 return x*f; 13 } 14 int main() 15 { 16 n=read();T=read(); 17 for(int i=1;i<=n;i++) 18 { 19 d=read();p=read();cnt=0; 20 if(d>T){printf("-1");return 0;} 21 for(int i=st;i<ed;i++) 22 { 23 if(a[i].p<p)cnt+=a[i].d; 24 else ed=i; 25 } 26 if(cnt<T)a[ed].p=p,a[ed].d=T-cnt,ed++; 27 while(st<ed) 28 { 29 if(a[st].d<=d)ans+=a[st].d*a[st].p,d-=a[st].d,st++; 30 else ans+=d*a[st].p,a[st].d-=d,d=0; 31 if(d<=0)break; 32 } 33 } 34 printf("%lld",ans); 35 return 0; 36 }