《花生采摘》解题报告 本文关键词：采摘，解题，花生，报告
《花生采摘》解题报告 本文简介：《花生采摘》解题报告Bysx349【摘要】核心算法思想：贪心主要数据结构：其他辅助知识：时间复杂度：空间复杂度：【题目大意】给定一个非空矩阵，每次都从中选择一个最大值并将其从矩阵中排除，将这些取出的数排序后计算其花费（相邻两数的花费是其在矩阵之间的曼哈顿距离），求在给定最大花费下，能取到的最大值的最
《花生采摘》解题报告 本文内容：
《花生采摘》解题报告
By
sx349
【摘要】
核心算法思想：贪心
主要数据结构：
其他辅助知识：
时间复杂度：
空间复杂度：
【题目大意】
给定一个非空矩阵，每次都从中选择一个最大值并将其从矩阵中排除，将这些取出的数排序后计算其花费（相邻两数的花费是其在矩阵之间的曼哈顿距离），求在给定最大花费下，能取到的最大值的最大总和。
【算法分析】
文中说道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
根据这一句话，我们直接就可以得出，这道题应该采用贪心的算法。
因此，我们先对数据进行从大到小的排序，然后每次都取其中的最大值。因为必须在规定的时间内回到路边，所以在每次取最大值时，首先判断在采摘了这一次之后是否有足够的时间回到路边，即(去采摘目标花生的时间)+(采摘那目标花生所用的1单位时间)+(从目标所在地往第一行的时间)Mid
do
Inc(I);
While
Value[J]J;
If
I0
Then
Begin
Inc(Top);
Value[Top]:=Map[I,J];
X[Top]:=I;Y[Top]:=J;
End;
End;
Sort(1,Top);
K:=K-2;
X[0]:=1;Y[0]:=Y[1];
T:=0;I:=1;Sum:=0;
While
TK
Then
Print(Sum);
Sum:=Sum+Value[I];
T:=T+X[I]-1;
Inc(I);
End;
End.
