《爷爷的罚金》解题报告

《《爷爷的罚金》解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《爷爷的罚金》解题报告Bysx349【问题描述】小Y的爷爷老Y是一个有名的鞋匠。老Y人很厚道，虽然年纪大了，但是工作还是很忙的，定单很多，以前很多手工计算的活都越来越难以完成，经常陪钱。小Y看在眼里急在心里，他想帮助爷爷做点事，当然是利用他的特长——计算机编程。他分析后发现爷爷有n个必须完成的订单，一天只能处理一个订单，但是一个订单可能需要很多天才能完成。对于第i个订单，整数Ti(1≤Ti≤1000)代表爷爷完成这件工作所需要的天数。但是，订单太多是需要付出代价的，每个客户都认为自己的订单应该被马上处理。因此对于第i件工作，在开始着手这件工作之前每天都要付罚金Si(1≤Si≤10000)。

2、现在，小Y想编一个程序来帮助爷爷找出所付罚金最少的订单处理次序。【输入文件】（shoemaker.in）输入文件第一行给出订单的总数n(1≤n≤1000)。接下来n行，第i行有两个整数，即完成第i件工作所需时间Ti和延迟这项工作每天需要交的罚金Si。【输出文件】（shoemaker.out）输出文件只有一行一个整数，即最少的罚金。【输入输出样例】shoemaker.inshoemaker.out9/943411000225542【问题分析】不妨先考虑这道题的一个简化版本——排队打水问题：有N个人正在排队打水，其中第i个人打水所用的时间为。请安排这些人打水的顺序，使得每个人等待的时间的总和，

3、即最小。对比排队打水问题和当前的问题可以发现，其实排队打水问题是当前问题在S均为1的情况下的一个特例。如何解答排队打水问题？考虑将上述式子展开得到：也就是说，排在越前面的人，他所用的打水时间就越多次成为后面的人的等待时间。因此，应该尽量将打水时间短的人放在队伍的前列。用数学语言来表达这个想法：不妨考虑打水队伍中的两个人i与j（i

4、下来，回过头看《爷爷的罚金》这道题。所有的S均为1的特例已经解决了，那么，能不能由此借鉴出该题的做法呢？由于S不为1，因此，现在要做的，是使得最小。一个最基础的想法是，依然尽可能的让时间短的订单排在序列的前列。显然，由于现在的式子结果与S有关，因此在同样按上述推理时必然会因为S的不同而导致结果不定（与的大小关系不定）。更进一步的想法是，既然这个式子与S和T均有关，不妨考虑每份订单的9/9“性价比”，即。如果将一份订单拆成份T值均为的订单，拆分过后的每一个新“订单”的S值均为1，原问题就转化成了排队打水问题。得出最终的序列后，根据上面的分析，同一份订单拆分出的新“订单”一定可以安排在连续的位

5、置，再将这些订单合并，问题又恢复到了当前问题。如果省略两个问题互相转化的那一步，可以发现，其实最后的排列顺序一定是按照不降序的。但是在将两个问题转化的过程中，由于订单的拆分，会出现一部分新“订单”，因为等待同属于一份原订单的其他新“订单”，而使得罚金增加的情况，从而使得在原问题转化为排队打水问题的过程中，总的“等待时间”增加了。但是，由于无论这些新“订单”在排队打水序列中的位置如何，增加的总时间总为，因此所有的排队打水序列修正合并为订单序列后，最优的排队打水序列依然会是最优的订单序列。同样的，也可以给出一个基于调整交换的证明。不妨假设当前已经存在一个订单序列（不一定是最优的）：考虑其中的两

6、个订单和，假设交换这两个订单前后总的罚金为和:可以发现，展开之后，第一项和第四项的值在交换前后不发生9/9改变，同样不发生改变的还有一项。不妨令：那么，可以得到：当且仅当时，应当交换这两份订单使得总罚金减小，因此：由此可以得出结论：如果序列当中任意相邻的两项满足，那么就一定可以通过交换这两份订单使得总罚金减小。而如果任意相邻的两项满足，那么任意交换这两个订单不会影响总罚金的大小。根据这个结论，再利用一下反证法：（1）显然，最优序列一定是存在的；（2）假设最优序列中存在相邻的两项的递减，那么一定可以将它9/9们交换使得总罚金减小形成更优的序列，与当前序列即为最优序列矛盾。（1）所以最优订单序

7、列中相邻的两项的一定是不降的，而整个最优订单序列一定是关于不降的一个序列。【算法实现】根据以上结论，可以得到一个颇为简单的算法：读入S与T之后，按照从小到大排序，然后逐个计算罚金即可。在大小比较时，为了避免实数比较的一些问题，可以将不等式两边通分转化为整数比较。时间复杂度：空间复杂度：【心得体会】（浅谈有关贪心策略的选择和对其证明的必要性）本题最终化归为一个简单明确的贪心结论，其思考过程就如同行文所述，是从排队打水问题之