自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 21:16:25，当前版本为作者最后更新于2024-06-18 22:05:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Source & Knowledge

2024 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

考察循环。

文字题解

【思路分析】

如果一张优惠券都不使用，最终花费的钱数就是 $S=a_1+a_2+\cdots+a_n$。

那么，我们希望最大化我们能够使用的优惠券的数目。一杯饮品使用一张优惠券，或全部使用优惠券支付，这杯饮品都无法再获得优惠券。因此，为了获得更多的优惠券，对于一杯奶茶，我们要么支付全价，要么尽可能使用优惠券。

同样，奶茶价格无论高低，购买一杯都最多获得一张优惠券，因此我们按照价格从低到高的顺序依次购买，价格低的全价支付获取优惠券，价格高的全部使用优惠券。

在 $1\sim n$ 范围内枚举 $i$，第 $1\sim i$ 杯奶茶全部支付全价，可以得到 $i$ 张优惠券。接着计算出 $i+1\sim n$ 杯奶茶的总价格 $t$，可以使用的优惠券数目 $u=\min(i,t)$。此时，需要支付的总价格为 $S-u$，通过枚举找到总价格的最低值输出即可。

若 $t$ 通过循环计算，时间复杂度为 $O(n^2)$；若提前计算总价，每次减去 $a_i$ 得到 $t$，时间复杂度为 $O(n)$。

视频题解