本文主要是介绍2004NOIP普及组真题 2. 花生采摘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
线上OJ:
【04NOIP普及组】花生采摘
核心思想:
1、本题为贪心即可。
2、因为本题严格限制了顺序,所以先把每个节点的花生数量按降序排序。然后逐一判断下一个花生是否需要去采摘即可
3、每一次采摘完,记录耗时 t 以及采集的花生总数 ans。同时考虑排序后的下一个节点,如果采摘后返回路边时间足够,则执行下一次采摘;如果采摘后来不及返回路边,则不再进行下一次采摘,本次直接返回路边即可。
4、注意,第一次是否需要采摘可进行特判。for 循环中从花生第二多的节点开始
题解代码:
#include <bits/stdc++.h>
using namespace std;const int N = 405;struct Node
{int x, y; // 第x行,第y列int n; // 的花生数量为n
};
Node node[N];bool cmp(Node a, Node b)
{return a.n > b. n; // 降序排序
}int m, n, k, cnt=0; // cnt用于记载node的数量int main()
{scanf("%d %d %d", &m, &n, &k);for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){node[++cnt].x = i; // 存储行node[cnt].y = j; // 存储列scanf("%d", &node[cnt].n); // 存储花生数量}sort(node + 1, node + 1 + cnt, cmp); // 对所有的节点按照n进行降序排序if(2 * node[1].x + 1 > k) // 如果采集第一次就无法返回,则输出0{printf("0\n");return 0;}int t = node[1].x + 1; // 如果第一次采集时间足够,则用t记录第一次采集已经耗费的时间,记得要把采摘的+1时间也算上int ans = node[1].n; // ans记录已经采集的花生总数for(int i = 2; i <= cnt; i++){ // 如果从当前i-1到下一个i,时间不足以完成走路+采摘+回到路边,则到此结束if(t + abs(node[i].x - node[i-1].x) + abs(node[i].y - node[i-1].y) + 1 + node[i].x > k)break;else // 如果从当前i-1到下一个i时间够,则,采摘第i个{t += abs(node[i].x - node[i-1].x) + abs(node[i].y - node[i-1].y) + 1; // 更新耗费时间tans += node[i].n; // 更新采摘数量 ans}}printf("%d\n", ans);return 0;
}
这篇关于2004NOIP普及组真题 2. 花生采摘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!