自动搬运

查看原文

来自洛谷，原作者为

	ButterflyDew life is hard

搬运于2025-08-24 21:37:00，当前版本为作者最后更新于2018-07-01 16:18:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一开始的贪心很容易想到要每次先给大钱，如果不够一步步拿小钱补充。

但最后小钱用完了可能产生浪费，万一大钱浪费一下可以更少呢。又看了看数据范围$N(1<=N<=20)$，心想怕不是个搜索。憋了一会儿搜索写不出来。最后看了题解才知道是贪心。

先说说这个题贪心的思维导向性在哪，没错就是这句话**“每一个面额都能整除所有比它大的面额”**，是不是感觉又奇怪又违和，感觉用不上？？

一般来讲，遇到这种看起来比较怪的条件，可以尝试这向贪心的方面想一想。哪怕证不出来也没关系，骗点分总不亏撒

下面正题，贪心策略及证明

策略

每一次给钱时，从大钱开始给，但每次给到要浪费钱的一次就不给了，用小一些的钱给。 给到已经没有小钱了以后，再给怎么也会产生浪费，就从小到大给，用面值尽可能小的钱产生浪费。

总结起来就是一句话：当需要产生浪费时，用面值尽可能小的钱产生

证明

命题：大钱产生的浪费一定不比小钱小

证明： 任取两个面值的钱分别为$ka,a$，$k$是正整数，在当前次还需要支付零用钱至少$X$

(1) 当浪费大钱$ka$时 设$X=b*ka+r$①

则浪费的钱数为$f=ka-r$②

(2)当浪费小钱$a$时 用掉一定的$ka$却不浪费当前次还需要支付的零用钱为$X'=r$ 设$X'=b'*a+r'$③

则浪费的钱数为$f'=a-r'$④

两者做差，$f-f'=(k-1)*a+r'-r$

由③得，$r'-r=-b'*a$

则$f-f'=(k-b'-1)*a$

因为$k,b'$均为正整数且$k>b'$，所以$f-f'>=0$

命题得证。

当然，我们肯定不能一次次的枚举每一周的给钱方案，否则会$T$两组。

考虑对情况进行加速，说是加速，其实也就是存储每周在某种情况下每个钱用了多少张，然后直接统计这种用钱情况可以重复多少次而已。

写的时候注意细节

露迭月喵~