【题解】喝可乐

发布时间:2023-01-28 11:34:36
贴主:易向晚来适
热度:1
正在讨论:P1048 - Buy Buy Buy 题目传送门

易向晚来适 2023-01-28

跟【最小开支】这题很像,但相对简单一些。

题意不难理解,两种选择:一种是一次性花 a 元喝一瓶可乐;另一种是花 b 元喝完之后返你 c 元。

⭐ 首先明确暴力会超时,因此我们考虑贪心的策略。

1️⃣ 不妨假设第一种性价比更高,即 a ≤ b - c,那我们只要把所有的钱都拿来买一次性的就好了。

买完之后剩下的钱一定小于 b,所以这一种可行的答案直接就是 n / a。

2️⃣ 另一种就是可回收的性价比更高,此时需要先做一个小小的处理:自扣 b 元

这样才能保证我们剩下的钱可以 随心所欲 的以 b - c 一罐的价格买可乐。

此时我们可以购买到 (n - b) / (b - c) 瓶,还剩 b + (n - b) % (b - c) 元。

然后再去买一次 b 元,返还 c 元,至此已经买了 (n - b) / (b - c) + 1 瓶,还剩 c + (n - b) % (b - c) 元。

但是剩下的钱是有可能可以继续购买一次性的,所以再用剩下的全部去买 a 就好了。

一个细节,第二种情况需要保证 n >= b 才可以计算,否则会 WA。

(0)

Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1