题解

分析题意后发现，要从起点到终点，最终会买 $n - 1$ 个单位的物质，那么我只需要判断，当前从 $i$ 到 $i + 1$ 这一步转移所需要的物资从哪个城邦买即可。

做法

​ 维护一个单调队列 $queue$，其中购买物资的价格依次上升。

​ 假设当前要从第 $i$ 个城邦走到第 $i + 1$ 个城邦，并且打算从第 $j$ 个城邦买当前转移的所需的物资（单位1），那么此时的花费为 $i - j + cost[j]$，如果此时从第 $j$ 买物资花费要大于 $cost[i]$ （即从第 $i$ 个城邦买单位 $1$ 的物资），那么对于所有的 $k \in [i, n - 1]$，要从第 $k$ 个 城邦走到第 $k + 1$ 个城邦所购买的物资一定是从 $i$ 购买要优于从 $j$，那么此时的 $j$ 对后面所有城邦都不会造成贡献了，此时直接在队列中删去即可。

题目名称

小红的物资调度

问题描述

在一片被战争蹂躏的土地上，小红被指派完成一项艰巨的任务：他要从联盟的首都出发，确保重要的物资安全运送到最前线的最后一个要塞。联盟的城邦沿着补给线线性排列，小红需要精心筹划在每个城邦的物资购买与运输计划。

从一个城邦到达相邻城邦会消耗一定量的物资。每个城邦都有物资出售，但价格不尽相同。小红可以根据需要在任何城邦购买任意数量的物资。不过，如果小红携带的物资超过基本需求量(基本需求量为1)，将会产生额外的运输成本，即每多携带一单位物资跨越到下一个城邦，就需要支付一单位的运输费。

小红希望以最低的成本安全抵达最后一个城邦。请计算小红完成任务所需的最小总花费。

输入格式

第一行包含一个正整数 $n$，代表城邦的个数。

第二行包含 $n$ 个由空格分隔的正整数 $p_1, p_2, ..., p_n$，代表沿途每个城邦的物资售价。

输出格式

输出一个整数，表示小红抵达最后一个城邦的最小总花费。

样例输入

4
1 3 2 4

样例输出

5

样例说明

在第 1 个城邦购买 2 单位物资，花费为 $1 \times 2 = 2$。

将 1 单位物资从第1个城邦运送到第 2 个城邦，花费为 1。

在第 2 个城邦不购买物资，因此花费为 0。

在第 3 个城邦购买 1 单位物资，花费为 $2 \times 1 = 2$。

总花费为物资购买成本加上运输成本，即 $2 + 1 + 2 = 5$。

评测数据与规模

对于 $100\%$ 的评测数据，满足 $1 \leq n \leq 10^5$，$1 \leq p_i \leq 10^9$。