《爷爷的罚金》解题报告

《爷爷的罚金》解题报告Bysx349【问题描述】小Y的爷爷老Y是一个有名的鞋匠。老Y人很厚道，虽然年纪大了，但是工作还是很忙的，定单很多，以前很多手工计算的活都越来越难以完成，经常陪钱。小Y看在眼里急在心里，他想帮助爷爷做点事，当然是利用他的特长——计算机编程。他分析后发现爷爷有n个必须完成的订单，一天只能处理一个订单，但是一个订单可能需要很多天才能完成。对于第i个订单，整数Ti(1≤Ti≤1000)代表爷爷完成这件工作所需要的天数。但是，订单太多是需要付出代价的，每个客户都认为自己的订单应该被马上处理。因此对于第i件工作，在开始着手这件工作之前每天都要付罚金Si(1≤Si≤10000)。现在，小Y想编一个程序来帮助爷爷找出所付罚金最少的订单处理次序。【输入文件】（shoemaker.in）输入文件第一行给出订单的总数n(1≤n≤1000)。接下来n行，第i行有两个整数，即完成第i件工作所需时间Ti和延迟这项工作每天需要交的罚金Si。【输出文件】（shoemaker.out）输出文件只有一行一个整数，即最少的罚金。【输入输出样例】shoemaker.inshoemaker.out43411000225542【问题分析】不妨先考虑这道题的一个简化版本——排队打水问题：有N个人正在排队打水，其中第i个人打水所用的时间为。请安排这些人打水的顺序，使得每个人等待的时间的总和，即最小。对比排队打水问题和当前的问题可以发现，其实排队打水问题是当前问题在S均为1的情况下的一个特例。如何解答排队打水问题？考虑将上述式子展开得到：也就是说，排在越前面的人，他所用的打水时间就越多次成为后面的人的等待时间。因此，应该尽量将打水时间短的人放在队伍的前列。用数学语言来表达这个想法：不妨考虑打水队伍中的两个人i与j（i<j）。如果他们的打水时间，那么必然可以交换这两个人，使得打水等待总时间变短。不妨设交换前的总时间为，而交换后的总时间为，那么有：因此，只要当前的打水队伍中存在满足上述条件的两个人，就必然可以进行一次调整，最终得到的序列，必然是一个按照打水时间不降序的队伍。接下来，回过头看《爷爷的罚金》这道题。所有的S均为1的特例已经解决了，那么，能不能由此借鉴出该题的做法呢？由于S不为1，因此，现在要做的，是使得最小。一个最基础的想法是，依然尽可能的让时间短的订单排在序列的前列。显然，由于现在的式子结果与S有关，因此在同样按上述推理时必然会因为S的不同而导致结果不定（与的大小关系不定）。更进一步的想法是，既然这个式子与S和T均有关，不妨考虑每份订单的“性价比”，即。如果将一份订单拆成份T值均为的订单，拆分过后的每一个新“订单”的S值均为1，原问题就转化成了排队打水问题。得出最终的序列后，根据上面的分析，同一份订单拆分出的新“订单”一定可以安排在连续的位置，再将这些订单合并，问题又恢复到了当前问题。如果省略两个问题互相转化的那一步，可以发现，其实最后的排列顺序一定是按照不降序的。但是在将两个问题转化的过程中，由于订单的拆分，会出现一部分新“订单”，因为等待同属于一份原订单的其他新“订单”，而使得罚金增加的情况，从而使得在原问题转化为排队打水问题的过程中，总的“等待时间”增加了。但是，由于无论这些新“订单”在排队打水序列中的位置如何，增加的总时间总为，因此所有的排队打水序列修正合并为订单序列后，最优的排队打水序列依然会是最优的订单序列。同样的，也可以给出一个基于调整交换的证明。不妨假设当前已经存在一个订单序列（不一定是最优的）：考虑其中的两个订单和，假设交换这两个订单前后总的罚金为和:可以发现，展开之后，第一项和第四项的值在交换前后不发生改变，同样不发生改变的还有一项。不妨令：那么，可以得到：当且仅当时，应当交换这两份订单使得总罚金减小，因此：由此可以得出结论：如果序列当中任意相邻的两项满足，那么就一定可以通过交换这两份订单使得总罚金减小。而如果任意相邻的两项满足，那么任意交换这两个订单不会影响总罚金的大小。根据这个结论，再利用一下反证法：显然，最优序列一定是存在的；假设最优序列中存在相邻的两项的递减，那么一定可以将它们交换使得总罚金减小形成更优的序列，与当前序列即为最优序列矛盾。所以最优订单序列中相邻的两项的一定是不降的，而整个最优订单序列一定是关于不降的一个序列。【算法实现】根据以上结论，可以得到一个颇为简单的算法：读入S与T之后，按照从小到大排序，然后逐个计算罚金即可。在大小比较时，为了避免实数比较的一些问题，可以将不等式两边通分转化为整数比较。时间复杂度：空间复杂度：【心得体会】（浅谈有关贪心策略的选择和对其证明的必要性）本题最终化归为一个简单明确的贪心结论，其思考过程就如同行文所述，是从排队打水问题之中获得的灵感。但在实战的过程中，有很多同学只是直接利用了这个结论，而并没有考虑去证明它的正确性。在信息学竞赛中，这确实是一个值得注意的地方。由于贪心算法往往十分简单，时间复杂度、编程复杂度在一定程度上都显著优于同样用于解决最优化问题的动态规划、搜索等其他算法，而且其可靠程度往往并不低，因此经常受到选手的青睐。但是，贪心算法的一个致命软肋就在于，一旦不能证明贪心算法的正确性，比如贪心算法本身是错误的只是凑巧在几个点上与数据相符，或者某种贪心策略只适用于某些有规律的特殊情形，又或者贪心算法只能保证得到较优值而非最优值，那么在比赛的过程中是采用这种贪心算法，还是选择其他算法，就是选手对于时间、成绩的一个博弈；退一步说，如果我们现在面对一个贪心算法能够解决我们面临的一部分小数据或特殊数据，我们是否应该花一点时间（这“一点时间”可长可短）去证明这个贪心算法的正确性，同样也是一个对于时间的博弈。总的来说，贪心算法适用的情况，一种是贪心算法本身就是问题的正确解法：这种情况下，是必须要花一点时间证明这个正确性的；另一种是随机化贪心构造或选择，通过多次不同决策得到多个较优值而取得最优值的做法：这种情况下，往往并不一定要保证贪心算法的正确性；但是，在面对一道题目时，贪心算法是否就是我们当前应该寻找的一种算法，依旧需要我们有清晰的大脑和丰富的经验来进行甄别，并不是一朝一夕就能练成，也不是三言两语就能讲清的。【Pascal参考程序】//Program:爷爷的罚金//PROG:shoemaker//LANG:PASCALProgramShoeMaker;Var N,I,Time,Ans:Longint; S,T:Array[0..1000]ofLongint; ProcedureSwap(A,B:Longint); Var TT:Longint; Begin TT:=S[A];S[A]:=S[B];S[B]:=TT; TT:=T[A];T[A]:=T[B];T[B]:=TT; End; ProcedureSort(L,R:Longint); Var I,J,MidS,MidT:Longint; Begin I:=L;J:=R;MidS:=S[(I+J)Div2];MidT:=T[(I+J)Div2]; Repeat WhileS[I]*MidT>T[I]*MidSdoInc(I); WhileS[J]*MidT<T[J]*MidSdoDec(J); IfI<=JThenBegin Swap(I,J); Inc(I);Dec(J); End; UntilI>J; IfL<JThenSort(L,J); IfI<RThenSort(I,R); End;Begin Assign(Input,'shoemaker.in');Assign(Output,'shoemaker.out');Reset(Input);Rewrite(Output);Read(N); ForI:=1to