首页分享【SWUST OJ 题解】348: 花生采摘 (Python)(C++)

【SWUST OJ 题解】348: 花生采摘 (Python)(C++)

来源：萌宠菠菠乐园时间：2025-10-16 05:07

题目描述

鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。

有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

从路边跳到最靠近路边（即第一行）的某棵花生植株；

从一棵植株跳到前后左右与之相邻的另一棵植株；

采摘一棵植株下的花生；

从最靠近路边（即第一行）的某棵花生植株跳回路边。

现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。

例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。
题例图

输入

输入的第一行包括三个整数，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表示该植株下没有花生。

输出

输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。

样例输入

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

1234567

样例输出

时空限制：1000ms/65535kb

思路分析：

首先读题意，

鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”

其实就是按照从大到小的顺序去摘花生，注意这里对于每一次采摘都是去摘田地里当前剩下植株中最大的（贪心思想），也就是说如果时间不够去就一个也不摘（输出0）。所以本题只需要模拟这么一个过程：

1. 找到接下来要去摘的植株位置（当前最大的那个）
2. 判断去到这个位置所需的时间（这里的时间其实就是 ∣ x 2 − x 1 ∣ + ∣ y 2 − y 1 ∣ left | x_2 - x_1 right | + left | y_2 - y_1 right | ∣x2−x1∣+∣y2−y1∣，也即曼哈顿距离）加上从这个位置返回路上所需时间（也即x坐标）再➕1（采摘用时）是否导致超出时间，如果超出了时间，就代表没办法摘该植株，这是答案就是之前所有已摘花生数量（不含本次）。
3. 当仍然剩下时间但是已经没有可以摘的植株（剩下植株花生数量都为0）时也结束。

可见，这个过程中主要在怎么确定每一次要找的最大值在哪？ 这里提供3种方法（更多方法欢迎前往本文相关文章部分查看洛谷题解）：

暴力遍历，每次需要知道下一个最大植株位置时便遍历一遍田地矩阵；建立一个结构体，预先存下植株坐标和花生数量，然后根据数量递减排序；建立一个哈希表，键为坐标，值为花生数量，按照花生数量递减排序，这样从头开始遍历判断时间限制，就是满足题意的采摘顺序。（在Python中其实也是将map转化为list进行的排序，也使用可优先队列自定义优先规则，思想同2）。

代码实现

Python版本（使用map）

# ---输入模块--- m, n, k = map(int, input().strip().split()) # 初始化矩阵 matrix = [] # 逐行读取矩阵 for _ in range(m): row = list(map(int, input().split())) matrix.append(row) # 或者生成器写法: matrix = [list(map(int, input().split())) for _ in range(m)] # ---输入模块结束--- # ---处理模块--- mp = {} # 建立字典 # 遍历矩阵，并将坐标（从(1,1)开始）和对应值添加到字典中 for i in range(m): for j in range(n): # 将坐标调整为从(1,1)开始 mp[(i + 1, j + 1)] = matrix[i][j] # 将字典中的键值对转换为列表（Python字典不可排序），并按照值进行降序排序 sorted_mp = sorted(mp.items(), key=lambda x: x[1], reverse=True) neededTime, sum, isFirst = 0, 0, 0 # 初始化一些变量 #while step <= k: # 原bug # 遍历已降序排序待采摘的花生的坐标与值，如果值不为0,检查去摘该花生所需时间够不够用，如果不够，break结束遍历 for coords, value in sorted_mp: if value != 0: if isFirst == 0 and neededTime + 2 * coords[0] + 1 <= k: prev = ((0, coords[1]), 0) ## 根据题意初始化第一个花生植株的前置植株 isFirst = 1 elif isFirst == 0: # 原来这里有bug，以为第一大不行要找第二大的，但是题意只要最大的 break neededTime += abs(coords[0] - prev[0][0]) + abs(coords[1] - prev[0][1]) + 1 ## 检查加上当前想去位置所需时间是否已经超过限制 if neededTime + coords[0] > k: ## 如果去了该位置，是否能返回路上 break ## 超过则直接结束遍历 sum += value ## 加上该位置的花生数 prev = (coords, value) ## 更新前置花生植株信息 else: break # ---处理结束--- ## ---输出答案--- print(sum)

python

12345678910111213141516171819202122232425262728293031323334353637383940414243 C++版本（使用结构体排序）（搬运）

#include<bits/stdc++.h>//万能头真的很好用！ using namespace std; int nowx,nowy,nowval; //模拟的时候的坐标，最后一个么，，好吧我懒，不想开一个数组存图…… int length;//保存所有有花生的植株的个数 int m,n,k; int ans; //答案 struct node//结构体存花生 {int x,y,val; //坐标和花生数 } que[400]; bool cmp(node x,node y)//排序函数，花生多的排前面 {return x.val>y.val; } int main() {ios::sync_with_stdio(0);cin>>m>>n>>k;for(int i=1; i<=m; i++)for(int j=1; j<=n; j++){cin>>nowval;if(nowval) //不为0{que[length].x=i;que[length].y=j;que[length++].val=nowval；}}sort(que,que+length,cmp);int i=0;nowy=que[0].y; //可以从路边最靠近第一颗花生的地方到田里去while(k>abs(que[i].x-nowx)+abs(que[i].y-nowy)&&i<length){if(k<nowx) //没时间出来了break;k-=(abs(que[i].x-nowx)+abs(que[i].y-nowy)+1);nowx=que[i].x;nowy=que[i].y;ans+=que[i].val;i++;//接着采花生}k-=nowx;//跑出来if(k<0)//时间不够ans-=que[i-1].val; //倒退回上一颗cout<<ans<<endl;return 0; }

cpp

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748

进一步了解本题：P1086 [NOIP2004 普及组] 花生采摘