网站可以做软件检测吗,网站开发方案及报价单,品牌网站建设毛尖c,广告语线上OJ#xff1a;
【04NOIP普及组】花生采摘
核心思想#xff1a;
1、本题为贪心即可。 2、因为本题严格限制了顺序#xff0c;所以先把每个节点的花生数量按降序排序。然后逐一判断下一个花生是否需要去采摘即可
3、每一次采摘完#xff0c;记录耗时 t 以及采集的花…线上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, cnt0; // 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;
}
