首页 > 分享 > 花生采摘算法

花生采摘算法

萌宠菠菠乐园
2025-05-23 08:02

文章目录 1 题目2 解析2.1 思路2.2 样例解释 3 参考代码

1 题目

采花生
时间限制 1000 ms 内存限制 16384 KB 代码长度限制 100 KB 判断程序 Standard (来自小小)
题目描述
鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说:“你先找出花生最多的植株，去采摘它的花生;然后再找出剩下的植株里花生最多的，去采摘它的花生;依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内,可以做下列四件事情中的一件：

从路边跳到最靠近路边（即第一行）的某棵花生植株；从一棵植株跳到前后左右与之相邻的另一棵植株；采摘一棵植株下的花生；从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？
注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如花生田里只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为 13, 7, 15, 9。多多在 21 个单位时间内，只能经过(4, 2)、(2, 5)、(5, 4)，最多可以采到 37 个花生。

输入描述:
输入包含多组数据，每组数据第一行包括三个整数 M（1≤M≤20）、N（1≤N≤20）和 K（0≤K≤1000），用空格隔开；表示花生田的大小为 M * N，多多采花生的限定时间为 K个单位时间。
紧接着 M 行，每行包括 N 个自然数 P（0≤P≤500），用空格隔开；表示花生田里植株下花生的数目，并且除了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

输出例子:
37

2 解析

2.1 思路

首先要理清题目信息： 1 从第一行开始，最后一行回去，从路边到田间不花时间，每采一次花生花费一个时间单位；2 题目要求是在从多到少采花生的前提下，能最多采花生。
步骤： 1，记录每个花生的坐标以及数量（用结构体vector向量存储，方便使用STL的sort排序）；2，按花生数量从大到小排序；3，枚举花生；如果本次采花生的花费（走路花费时间+采摘时间+返回时间【只做比较，不计入临时采花生的总花费】）小于或等于规定时间，则把本次采摘的数量计入采摘总量，继续循环；否则，结束循环。走路花费时间：（行列坐标差）【第一次采摘时的走路花费只计入列坐标的值】；采摘时间：【1个时间单位】；返回路边的时间（列坐标的值【要经过第一行到达路边】））小于或等于规定时间，则把本次采摘的数量计入采摘总量； 4 输出最后采摘的总数量。

2.2 样例解释

设（x,y）：(行，列)。

1 从（0，2）【路边】出发到（4，2）【15处】；花费（走路：4 + 采摘：1 + 返回：4）= 9 < 21，累计花费cost = 5,计入总量ans = 15; 2 从（4，2）【15处】出发到（2, 5）【13处】；花费（走路：5 + 采摘：1 + 返回：2）= 8 + 5 < 21,累计花费cost = 5 + 6 = 11,计入总量ans = 28; 3 从（2, 5）【13处】出发到（5，4）【9处】；花费（走路：4 + 采摘：1 + 返回：5）= 9 + 11 < 21,累计花费cost = 11 + 5 = 16,计入总量ans = 37; 4 从（5 , 4）【13处】出发到（3，7）【9处】；花费（走路：5 + 采摘：1 + 返回：3）= 9 + 16 > 21, 超过规定时间，不计入总量； 5 输出答案：37

3 参考代码

/* * 详解： */ #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using std::vector; using std::sort; struct Peanut{ int x;//列 int y;//行 int cnt;//个数 Peanut(int _x, int _y, int _cnt):x(_x),y(_y),cnt(_cnt){}//构造函数 }; vector<Peanut> p; bool cmp(Peanut a, Peanut b){ return a.cnt > b.cnt; } int main(int argc, char const *argv[]){ int m, n, k; while(scanf("%d%d%d", &m, &n, &k) != EOF){ p.clear();//清空上次存储的花生信息 int tempCnt; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &tempCnt); if(tempCnt > 0){ p.push_back(Peanut(i, j, tempCnt)); } } } sort(p.begin(), p.end(), cmp);//按采摘总数从大到小排序 int cost = 0; int ans = 0; for (int i = 0; i < p.size(); ++i) { if(i == 0){ cost += p[i].x + 1;//每次采花生所用时间（走路+采花生） }else{ cost += abs(p[i].x - p[i-1].x) + abs(p[i].y - p[i-1].y) + 1; } if(cost + p[i].x > k){//如果本次采花生+回到路上的时间大于规定时间， break;// 本次采摘的花生数量不计入采摘总数 }else{//在规定时间范围内，计入采摘总数 ans += p[i].cnt; } } printf("%dn", ans); } return 0; } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162