202406 F

览遍千秋 · 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)。