《花生采摘》解题报告
By sx349
【摘要】
核心算法思想：贪心
主要数据结构：
其他辅助知识：
时间复杂度：O (N log N )
空间复杂度：O (N 2)
【题目大意】
给定一个非空矩阵，每次都从中选择一个最大值并将其从矩阵中排除，将这些取出的数排序后计算其花费（相邻两数的花费是其在矩阵之间的曼哈顿距离），求在给定最大花费下，能取到的最大值的最大总和。
【算法分析】
文中说道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 根据这一句话，我们直接就可以得出，这道题应该采用贪心的算法。
因此，我们先对数据进行从大到小的排序，然后每次都取其中的最大值。因为必须在规定的时间内回到路边，所以在每次取最大值时，首先判断在采摘了这一次之后是否有足够的时间回到路边，即(去采摘目标花生的时间)+(采摘那目标花生所用的1单位时间)+(从目标所在地往第一行的时间)
由于去摘花生必须从路边进入花生田和从花生田出来，所以我们可以先减去2个单位时间，再将剩下的时间进行模拟。
【心得体会】
花生采摘是一道典型的贪心问题，也是一道典型的简单题（因此这道题的算法分析也只能这样简单了„„）。但是这道题有一个区别于其他问题的地方：在解决问题的过程中，主要部分（连续取最大值）的时间复杂度只需要O (N ) ，而排序却花费了O (N log N ) 的时间复杂度。
这一点确实是在许多情况下无法回避的一个问题。我一直记得我们平时上课的计算机书上有一个简单的例子：给你一些电话号码，让你去寻找某一个指定的号码。书上的解释是用二分查找，但是我们来考虑一下，二分查找合适吗？当然，如果是在有序的情况下，二分的复杂度是O (logN ) ，但是，在无序的情况下，二分必须要在排序好后才能解决，那么时间复杂度就上升到了O (N log N log N ) ，因为除了少部分特殊的排序之外，因此不可避免地导致了O (N log N ) 的排序复杂度。如此一来，就超过了顺序查找的O (N ) 复杂度了。难道排
序的合理性就此受到了质疑了吗？当然不是，如果是查找多次的话，二分查找的时间复杂度就是O (N log N ) ，而顺序查找则飙升到了O (N 2) 。由此我们可以得出这样一个结论：预处理操作的效率随着预处理所得到的数据的使用率的提高而提高。
这又引出了这样一个怪异的想法：如果我找到了针对某个问题的一个时间复杂度仅为O (1)的主算法，那么我是不是就一定能解决它呢？显然不是。如果这个问题的输入达到了上千万乃至上亿，单单读入的复杂度就已经使程序罢工了。同样的，我也曾经有过因为输出过多而导致超时的经历。
因此，输入、输出、排序乃至其他一些游离于主算法之外的东西，有时反而成为了一个问题的决定点，这种出人意料的场景也着实是值得我们思考的。
【附录】
【问题描述 】
鲁滨逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁滨逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网络（如图1）。有经验的多多一眼就能看出，每株花生植株下的花生有多少。
为了训练多多的算术，鲁滨逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
路
4 5
图1
图2
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
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 个非负整数, 也用空格隔开;
第i+1行的第j 个整数P ij (0
[输出文件]
输出文件peanuts.out 包括一行.
这一行只包含一个整数，即在限定时间内，多多最多可以采到的花生的个数。
[样例输入]
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
[样例输出1]
37
[样例输入2]
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
[样例输出2]
28
【源程序清单】
{
PROG: Peanuts
LANG: PASCAL
ID: xyj-flash
}
Program Peanuts;
Var
X,Y ,Value:Array[0.400] of Longint;
Map:Array[1..20,1..20] of Longint;
M,N,K,I,J,Top,T,Sum:Longint;
Procedure Sort(L,R:Longint);
Var
I,J,Mid:Longint;
Begin
I:=L;J:=R;Mid:=Value[(L+R) Div 2]; Repeat
While Value[I]>Mid do Inc(I); While Value[J]
Value[0]:=Value[I];
Value[I]:=Value[J];
Value[J]:=Value[0];
X[0]:=X[I];X[I]:=X[J];X[J]:=X[0]; Y[0]:=Y[I];Y[I]:=Y[J];Y[J]:=Y[0]; Inc(I);Dec(J);
End;
Until I>J;
If I
If L
End;
Procedure Print(K:Longint); Begin
Writeln(K);
Halt;
End;
Begin
Read(M,N,K);
Top:=0;
For I:=1 to M do
For J:=1 to N do Begin Read(Map[I,J]);
If Map[I,J]0 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 T
T:=T+X[I]-X[I-1]+Y[I]-Y[I-1]+1; If T+X[I]-1>K Then Print(Sum); Sum:=Sum+Value[I];
T:=T+X[I]-1;
Inc(I);
End;
End.
《花生采摘》解题报告
By sx349
【摘要】
核心算法思想：贪心
主要数据结构：
其他辅助知识：
时间复杂度：O (N log N )
空间复杂度：O (N 2)
【题目大意】
给定一个非空矩阵，每次都从中选择一个最大值并将其从矩阵中排除，将这些取出的数排序后计算其花费（相邻两数的花费是其在矩阵之间的曼哈顿距离），求在给定最大花费下，能取到的最大值的最大总和。
【算法分析】
文中说道：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 根据这一句话，我们直接就可以得出，这道题应该采用贪心的算法。
因此，我们先对数据进行从大到小的排序，然后每次都取其中的最大值。因为必须在规定的时间内回到路边，所以在每次取最大值时，首先判断在采摘了这一次之后是否有足够的时间回到路边，即(去采摘目标花生的时间)+(采摘那目标花生所用的1单位时间)+(从目标所在地往第一行的时间)
由于去摘花生必须从路边进入花生田和从花生田出来，所以我们可以先减去2个单位时间，再将剩下的时间进行模拟。
【心得体会】
花生采摘是一道典型的贪心问题，也是一道典型的简单题（因此这道题的算法分析也只能这样简单了„„）。但是这道题有一个区别于其他问题的地方：在解决问题的过程中，主要部分（连续取最大值）的时间复杂度只需要O (N ) ，而排序却花费了O (N log N ) 的时间复杂度。
这一点确实是在许多情况下无法回避的一个问题。我一直记得我们平时上课的计算机书上有一个简单的例子：给你一些电话号码，让你去寻找某一个指定的号码。书上的解释是用二分查找，但是我们来考虑一下，二分查找合适吗？当然，如果是在有序的情况下，二分的复杂度是O (logN ) ，但是，在无序的情况下，二分必须要在排序好后才能解决，那么时间复杂度就上升到了O (N log N log N ) ，因为除了少部分特殊的排序之外，因此不可避免地导致了O (N log N ) 的排序复杂度。如此一来，就超过了顺序查找的O (N ) 复杂度了。难道排
序的合理性就此受到了质疑了吗？当然不是，如果是查找多次的话，二分查找的时间复杂度就是O (N log N ) ，而顺序查找则飙升到了O (N 2) 。由此我们可以得出这样一个结论：预处理操作的效率随着预处理所得到的数据的使用率的提高而提高。
这又引出了这样一个怪异的想法：如果我找到了针对某个问题的一个时间复杂度仅为O (1)的主算法，那么我是不是就一定能解决它呢？显然不是。如果这个问题的输入达到了上千万乃至上亿，单单读入的复杂度就已经使程序罢工了。同样的，我也曾经有过因为输出过多而导致超时的经历。
因此，输入、输出、排序乃至其他一些游离于主算法之外的东西，有时反而成为了一个问题的决定点，这种出人意料的场景也着实是值得我们思考的。
【附录】
【问题描述 】
鲁滨逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁滨逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网络（如图1）。有经验的多多一眼就能看出，每株花生植株下的花生有多少。
为了训练多多的算术，鲁滨逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
路
4 5
图1
图2
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
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 个非负整数, 也用空格隔开;
第i+1行的第j 个整数P ij (0
[输出文件]
输出文件peanuts.out 包括一行.
这一行只包含一个整数，即在限定时间内，多多最多可以采到的花生的个数。
[样例输入]
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
[样例输出1]
37
[样例输入2]
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
[样例输出2]
28
【源程序清单】
{
PROG: Peanuts
LANG: PASCAL
ID: xyj-flash
}
Program Peanuts;
Var
X,Y ,Value:Array[0.400] of Longint;
Map:Array[1..20,1..20] of Longint;
M,N,K,I,J,Top,T,Sum:Longint;
Procedure Sort(L,R:Longint);
Var
I,J,Mid:Longint;
Begin
I:=L;J:=R;Mid:=Value[(L+R) Div 2]; Repeat
While Value[I]>Mid do Inc(I); While Value[J]
Value[0]:=Value[I];
Value[I]:=Value[J];
Value[J]:=Value[0];
X[0]:=X[I];X[I]:=X[J];X[J]:=X[0]; Y[0]:=Y[I];Y[I]:=Y[J];Y[J]:=Y[0]; Inc(I);Dec(J);
End;
Until I>J;
If I
If L
End;
Procedure Print(K:Longint); Begin
Writeln(K);
Halt;
End;
Begin
Read(M,N,K);
Top:=0;
For I:=1 to M do
For J:=1 to N do Begin Read(Map[I,J]);
If Map[I,J]0 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 T
T:=T+X[I]-X[I-1]+Y[I]-Y[I-1]+1; If T+X[I]-1>K Then Print(Sum); Sum:=Sum+Value[I];
T:=T+X[I]-1;
Inc(I);
End;
End.