信息学奥赛一本通题目解析：1927：【04NOIP普及组】花生采摘（模拟）
描述
鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
例如在图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表示该植株下没有花生。
输出
包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。
样例输入
样例 #1： 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 样例 #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
样例输出
样例 #1： 37 样例 #2： 28
【解题思路】
解题思路可以概括为以下几个步骤：
1. 理解问题和约束条件首先，需要准确理解题目描述和要求，即在限定的时间内，多多需要采摘尽可能多的花生。多多可以从路边跳到任何一棵花生植株，从一个植株跳到相邻的植株，采摘植株下的花生，以及从植株跳回路边。每种动作均消耗一定的时间单位。
2. 优先考虑花生多的植株题目的关键在于优先采摘那些花生较多的植株，以在有限的时间内最大化采摘到的花生数量。这意味着需要对花生植株根据其下的花生数量进行排序。
3. 计算时间和路径考虑到时间限制，每次采摘后，都需要计算包括跳跃、采摘和返回路边所需的总时间。这个总时间包括从当前位置到下一棵植株的跳跃时间、采摘时间（常数，假设为1个时间单位）以及最终从植株返回路边的时间。每次移动后都要检查是否有足够的时间完成下一次采摘，如果时间不够，则应该停止采摘。
【代码步骤】
数据结构选择：定义一个Node结构体来存储每个花生植株的位置(x, y)和该位置的花生数(n)。这样可以方便地处理每个植株的信息。
输入处理：通过双层循环读入花生田的尺寸(m, n)和每个植株的花生数量。对于每个植株，如果其花生数量大于0，则将其信息存储在Node数组中。
排序：使用std::sort()函数和自定义的比较函数compare，根据花生数量对所有植株进行降序排序。这一步是优化搜索顺序的关键，确保优先采摘花生数量多的植株。
采摘逻辑：从花生最多的植株开始，计算包括采摘在内的总时间消耗，确保在给定的时间限制k内返回。这一步骤涉及对每次采摘后剩余时间的精确计算。
时间和返回条件：对每个植株，计算从当前位置到该植株的移动时间、采摘时间(恒为1)以及返回边缘的时间。如果总时间超出限制，则停止采摘。
输出结果：最后，输出在时间限制内可以采摘的最大花生数量。
【关键点】
关键点排序优化：通过sort()进行排序，排序确保了采摘顺序是按照花生数量从多到少的，这是最优化采摘策略的关键。
时间管理：核心算法部分监控时间消耗，每步移动和采摘后都要检查总时间是否超出限制。这包括了到达每棵植株的时间、采摘时间以及返回路边的时间。
早停机制：如果在任何时刻计算出剩余时间不足以采摘下一株植株并返回起点，算法将停止采摘过程。这是一种高效的时间利用策略，确保在时间耗尽之前尽可能多地采摘花生。
边界条件处理：算法开始时对第一株植株的特殊处理（即考虑从起点直接到达第一株植株的时间），以及随后植株间移动的时间计算。
【代码实现】
#include <bits/stdc++.h>
using namespace std;
#define N 25
struct Node {
int x, y, n;
};
bool compare(const Node& a, const Node& b) {
return a.n > b.n;
}
int main() {
Node a[405];
int an = 0, m, n, k, t = 0, ans = 0;
cin >> m >> n >> k;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j) {
a[++an].x = i;
a[an].y = j;
cin >> a[an].n;
}
sort(a + 1, a + an + 1, compare);
t = a[1].x + 1;
if(t + a[1].x > k) {
cout << 0;
return 0;
}
ans += a[1].n;
for(int i = 2; i <= an; ++i) {
if(t + abs(a[i].x-a[i-1].x) + abs(a[i].y-a[i-1].y) + 1 + a[i].x > k)
break;
else {
t += abs(a[i].x-a[i-1].x) + abs(a[i].y-a[i-1].y) + 1;
ans += a[i].n;
}
}
cout << ans;
return 0;
}
相关知识
信息学奥赛一本通题目解析：1927：【04NOIP普及组】花生采摘（模拟）
P1086 [NOIP2004 普及组] 花生采摘
P1086 [NOIP2004 普及组] 花生采摘（模拟）
[NOIP普及组 2004] 花生采摘 {快速排序}
P1086 花生采摘(C++)
【NOIP2004普及组】花生采摘
洛谷 P1086 花生采摘 题解
NOIP2004 花生采摘 题解
【NOIP2004PJ】花生采摘
SWUSTOJ #348 花生采摘
网址: 信息学奥赛一本通题目解析：1927：【04NOIP普及组】花生采摘（模拟） https://m.mcbbbk.com/newsview558135.html
| 上一篇: 洛谷 P1086 [NOIP20 |
下一篇: Pat乙级练习1采花生 |
