CF853D Michael and Charging Stations

Michael 刚买了一辆新的电动汽车用于在城市中通勤。Michael 不喜欢太累，因此他每天只会去他的两个工作之一。 Michael 的一天从给电动车充电开始，这样他才能往返于工作和家之间。如果去第一个工作地点，他需要花费 $1000$ 布尔充电，如果去第二个工作地点，则需要花费 $2000$ 布尔。 他使用的充电站有一个积分卡的忠诚计划。积分卡上可以有一些非负的积分（bonus burles）。每当顾客需要购买价值 $x$ 布尔的商品时，可以用积分卡上的积分支付 $y$ 布尔（$0 \leq y \leq x$），且 $y$ 不超过当前积分卡余额。这样，他需要用现金支付 $x-y$ 布尔，积分卡余额减少 $y$ 积分。 如果顾客用现金支付了全部金额（即 $y=0$），那么会返还 10% 的金额到积分卡。例如，积分卡余额会增加 $\left\lfloor \frac{x}{10} \right\rfloor$ 积分。最开始，积分卡余额为 0。 Michael 已经计划好了接下来的 $n$ 天，并且他知道每天充电的花费。请你帮 Michael 计算，在最优使用积分卡的情况下，他最少需要用现金支付多少布尔。你可以在任意一天，用现金支付任意部分金额。最后不要求用光所有积分。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 300000$），表示 Michael 计划了多少天。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$a_i=1000$ 或 $a_i=2000$），其中 $a_i$ 表示第 $i$ 天的充电费用。

输出一个整数，表示 Michael 最少需要用现金支付多少布尔。

在第一个样例中，最优的做法是前两天都用现金支付，共花费 3000 布尔，并获得 300 积分返还。然后第三天只需要支付 700 布尔现金，其余部分用积分抵扣。 在第二个样例中，最优做法是前五天都用现金支付，获得 1000 积分返还，第六天即可全部用积分支付，无需再支付现金。 由 ChatGPT 5 翻译