题目描述

军队每从一个国家移动到一个相邻国家就需要消耗1单位的粮食，每个国家都会售卖粮食，每单位价格为$a_i$，塔子哥可以购买任意单位的粮食。 塔子哥想要用最少的花费使得军队到达$n$号国家，但是她希望每个国家的粮食不要购买太多，即重复吃一个国家粮食的次数的最大值最小。 塔子哥想知道一种她要到达$n$号国家且满足上述条件的粮食购买方案。(如果有多种答案，可以输出任意一种)

思路

反悔贪心。 考虑当前在第 i 个城市，即将前往第 i+1 个城市，手上没有粮食，需要在第 [1, i] 个城市中选择一个城市购买1单位。

Q：应该选择哪个呢？

A：要求花费最少，所以选择粮食价格最低的那个城市

Q：如果有多个城市的花费都一样最低呢？