问题描述

• 一辆汽车将要从A城驶往B城。由于两城市之间的距离较远，即使这辆汽车在A城加满油，也无法在中途不加油的情况下抵达B城。幸运的是，两城之间的公路设有一些加油站，可以为汽车提供加油服务。 设两城之间的距离为 ，那么中间每 个单位距离就设有一座加油站（起点与终点没有）。汽车在加满油时，能行驶 个单位距离，为了保证汽车能顺利抵达B城，汽车必须在汽油耗尽前找到加油站进行加油。 由于每座加油站的汽油销售价格不同，这个汽车的驾驶员在出发前记录下了每个加油站的汽油销售价格，并给汽车加满了油。在第 个加油站需花费 的价格加满油（只能提供加满的服务）。为了尽量减少在旅途中的开销，驾驶员请聪明的你编程求出他最少要花费多少油钱。

输入格式

• 输入共两行。

• 第一行两个整数，输入用空格隔开的 和 。 第二行 个整数，第 个整数为 ，用空格隔开。

• 输出格式

• 共一行一个整数，即最少的花费。

• 样例输入 5 2 2 4 8 6

• 样例输出 10

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;
long long i,n,d,a[N],v[N],sum[N],mi,k,ans,mo;
int main()
{
    cin>>n>>d;
    for(i=1;i<n;i++)v[i]=1;
    for(i=1;i<n;i++)cin>>a[i];
    mi=a[1],k=1;
    for(i=1;i<n-1;i++)
    {
        if(a[i]>=mi){
			sum[k]+=v[i];
		}
        else
        {
            k=i;
			mi=a[i];
			sum[i]+=v[i];
        }
    }
    for(i=1;i<=n;i++)
    {
		ans+=sum[i];
	}
    cout<<ans;
    return 0;
}