花生采摘解题报告
5页1、花生采摘解题报告By sx349 【摘要】核心算法思想:贪心主要数据结构:其他辅助知识:时间复杂度:空间复杂度:【题目大意】给定一个非空矩阵,每次都从中选择一个最大值并将其从矩阵中排除,将这些取出的数排序后计算其花费(相邻两数的花费是其在矩阵之间的曼哈顿距离),求在给定最大花费下,能取到的最大值的最大总和。【算法分析】文中说道:“你先找出花生最多的植株,去采摘它的花生;然后再找出剩下的植株里花生最多的,去采摘它的花生;依此类推,不过你一定要在我限定的时间内回到路边。”根据这一句话,我们直接就可以得出,这道题应该采用贪心的算法。因此,我们先对数据进行从大到小的排序,然后每次都取其中的最大值。因为必须在规定的时间内回到路边,所以在每次取最大值时,首先判断在采摘了这一次之后是否有足够的时间回到路边,即(去采摘目标花生的时间)+(采摘那目标花生所用的1单位时间)+(从目标所在地往第一行的时间)=(剩下的单位时间)。若条件不满足就停止,若满足就继续采摘。由于去摘花生必须从路边进入花生田和从花生田出来,所以我们可以先减去2个单位时间,再将剩下的时间进行模拟。【心得体会】花生采摘是一道典型的贪心问题
2、,也是一道典型的简单题(因此这道题的算法分析也只能这样简单了)。但是这道题有一个区别于其他问题的地方:在解决问题的过程中,主要部分(连续取最大值)的时间复杂度只需要,而排序却花费了的时间复杂度。这一点确实是在许多情况下无法回避的一个问题。我一直记得我们平时上课的计算机书上有一个简单的例子:给你一些电话号码,让你去寻找某一个指定的号码。书上的解释是用二分查找,但是我们来考虑一下,二分查找合适吗?当然,如果是在有序的情况下,二分的复杂度是,但是,在无序的情况下,二分必须要在排序好后才能解决,那么时间复杂度就上升到了,因为除了少部分特殊的排序之外,因此不可避免地导致了的排序复杂度。如此一来,就超过了顺序查找的复杂度了。难道排序的合理性就此受到了质疑了吗?当然不是,如果是查找多次的话,二分查找的时间复杂度就是,而顺序查找则飙升到了。由此我们可以得出这样一个结论:预处理操作的效率随着预处理所得到的数据的使用率的提高而提高。这又引出了这样一个怪异的想法:如果我找到了针对某个问题的一个时间复杂度仅为的主算法,那么我是不是就一定能解决它呢?显然不是。如果这个问题的输入达到了上千万乃至上亿,单单读入的复
《花生采摘解题报告》由会员新**分享,可在线阅读,更多相关《花生采摘解题报告》请在金锄头文库上搜索。
妇联庆祝三八妇女节活动方案
平移和旋转 (2)
常用日语音译
2022年幼儿园晨午检管理制度
高考语文备考答题技巧
优秀员工颁奖大会主持词
2023年小区物业客服工作总结(2篇).doc
2022年校庆的优秀讲话稿7篇
大班家长会发言稿6篇
农滴滴被实名举报
2023年收银员实习总结(3篇).doc
香格里拉市关于成立精细化工研发公司策划书参考模板
建筑行业上海某水厂原水管道扩建工程施工组织设计方案
如如何创设幼儿园环境
湘少版六年级英语段考试卷
2022年水务局规章制度
2022二级建造师-二建建筑工程实务考前拔高名师测验卷37(附答案解析)
2023年八年级上册初中生物教学计划3篇人教版八年级上生物教学计划
新形势下蚌埠地区淮河水运发展分析
北京金石信诚电子科技有限公司车间管理制度
2023-07-08 19页
2023-02-03 6页
2023-09-30 4页
2023-10-31 49页
2023-03-04 12页
2022-09-10 25页
2024-01-07 16页
2023-07-11 23页
2023-10-28 1页
2023-01-19 10页