《花生采摘》解题报告.doc

花生采摘解题报告By sx349 【摘要】核心算法思想：贪心主要数据结构：其他辅助知识：时间复杂度：空间复杂度：【题目大意】给定一个非空矩阵，每次都从中选择一个最大值并将其从矩阵中排除，将这些取出的数排序后计算其花费（相邻两数的花费是其在矩阵之间的曼哈顿距离），求在给定最大花费下，能取到的最大值的最大总和。【算法分析】文中说道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”根据这一句话，我们直接就可以得出，这道题应该采用贪心的算法。因此，我们先对数据进行从大到小的排序，然后每次都取其中的最大值。因为必须在规定的时间内回到路边，所以在每次取最大值时，首先判断在采摘了这一次之后是否有足够的时间回到路边，即(去采摘目标花生的时间)+(采摘那目标花生所用的1单位时间)+(从目标所在地往第一行的时间)<=(剩下的单位时间)。若条件不满足就停止，若满足就继续采摘。由于去摘花生必须从路边进入花生田和从花生田出来，所以我们可以先减去2个单位时间，再将剩下的时间进行模拟。【心得体会】花生采摘是一道典型的贪心问题，也是一道典型的简单题（因此这道题的算法分析也只能这样简单了）。但是这道题有一个区别于其他问题的地方：在解决问题的过程中，主要部分（连续取最大值）的时间复杂度只需要，而排序却花费了的时间复杂度。这一点确实是在许多情况下无法回避的一个问题。我一直记得我们平时上课的计算机书上有一个简单的例子：给你一些电话号码，让你去寻找某一个指定的号码。书上的解释是用二分查找，但是我们来考虑一下，二分查找合适吗？当然，如果是在有序的情况下，二分的复杂度是，但是，在无序的情况下，二分必须要在排序好后才能解决，那么时间复杂度就上升到了，因为除了少部分特殊的排序之外，因此不可避免地导致了的排序复杂度。如此一来，就超过了顺序查找的复杂度了。难道排序的合理性就此受到了质疑了吗？当然不是，如果是查找多次的话，二分查找的时间复杂度就是，而顺序查找则飙升到了。由此我们可以得出这样一个结论：预处理操作的效率随着预处理所得到的数据的使用率的提高而提高。这又引出了这样一个怪异的想法：如果我找到了针对某个问题的一个时间复杂度仅为的主算法，那么我是不是就一定能解决它呢？显然不是。如果这个问题的输入达到了上千万乃至上亿，单单读入的复杂度就已经使程序罢工了。同样的，我也曾经有过因为输出过多而导致超时的经历。因此，输入、输出、排序乃至其他一些游离于主算法之外的东西，有时反而成为了一个问题的决定点，这种出人意料的场景也着实是值得我们思考的。【附录】 2005选拔赛第一轮 花生采摘 peanuts.pas/dpr/c/cpp 输入文件名：peanuts .in 输出文件名：peanuts.ou 【问题描述 】鲁滨逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。鲁滨逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网络（如图1）。有经验的多多一眼就能看出，每株花生植株下的花生有多少。为了训练多多的算术，鲁滨逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”2465137134625路图12465137134625路图2151379我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1） 从路边跳到最靠近路边（即第一行）的某棵花生植株；2） 从一棵植株跳到前后左右与之相邻的另一棵植株；3） 采摘一棵植株下的花生；4） 从最靠近路边（即第一行）的某棵花生植株跳回到路边。现在给定一块花生田的大小和花生的分布，请问在限定的时间内，多多最多可以采到多少个花生？注意可能只有部分的植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图二所示的花生田里，只有位于（2，5），（3，7），（4，2），（5，4）的植株下长有花生，个数分别为13，7，15，9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。输入文件输入文件peanuts.in的第一行包括三个整数，M，N和K，用空格隔开；表示花生田的大小为M*N（1<=M，N<=20），多多采花生的限定时间为K（0<=K<=1000）个单位时间.接下来的M行,每行包括N个非负整数,也用空格隔开;第i+1行的第j个整数Pij(0<=Pij<=500)表示花生田里植株(i,j)下花生的数目,0表示该植株下没有花生。输出文件输出文件peanuts.out包括一行.这一行只包含一个整数，即在限定时间内，多多最多可以采到的花生的个数。样例输入6 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0样例输出137样例输入26 7 200 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0样例输出228【源程序清单】PROG: PeanutsLANG: PASCALID: xyj-flashProgram Peanuts;VarX,Y,Value:Array0.400 of Longint;Map:Array1.20,1.20 of Longint;M,N,K,I,J,Top,T,Sum:Longint;Procedure Sort(L,R:Longint);VarI,J,Mid:Longint;BeginI:=L;J:=R;Mid:=Value(L+R) Div 2;RepeatWhile ValueI>Mid do Inc(I);While ValueJ<Mid do Dec(J);If I<=J Then BeginValue0:=ValueI;ValueI:=ValueJ;ValueJ:=Value0;X0:=XI;XI:=XJ;XJ:=X0;Y0:=YI;YI:=YJ;YJ:=Y0;Inc(I);Dec(J);End;Until I>J;If I<R Then Sort(I,R);If L<J Then Sort(L,J);End;Procedure Print(K:Longint);BeginWriteln(K);Halt;End;BeginRead(M,N,K);Top:=0;For I:=1 to M do For J:=1 to N do BeginRead(MapI,J);If MapI,J<>0 Then BeginInc(Top);ValueTop:=MapI,J;XTop:=I;YTop:=J;End;End;Sort(1,Top);K:=K-2;X0:=1;Y0:=Y1;T:=0;I:=1;Sum:=0;While T<K do BeginT:=T+XI-XI-1+YI-YI-1+1;If T+XI-1>K Then Print(Sum);Sum:=Sum+ValueI;T:=T+XI-1;Inc(I);End;End.