算法笔试模拟题精解之“吃奶酪”

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

https://developer.aliyun.com/coding

本文为大家介绍其中的 第49题：吃奶酪 的题目解析，具体如下：

题目描述

题目等级：容易

知识点：贪心、枚举

查看题目：吃奶酪

Tom和Jerry都很喜欢吃奶酪，现在有n块奶酪散落在坐标轴上(1<=n<=100000)，他们分别在a1,a2,a3...an(1<=ai<=100000,一个点可以有多块奶酪)上，Tom和Jerry分别在1和100000两个点上，他们每走一步需要花费1s，问他们拿到所有的奶酪至少要花费多少时间

输入奶酪数量n，和n个奶酪的坐标

输出一个数，表示他们拿到所有奶酪所用的最短时间

示例1

输入：

4

[350,2000,80000,99999]

输出：

20000

解题方法

根据题意，如果要花费最少时间，则每个奶酪都让离奶酪最近的人去拿，因此，坐标<=50000的奶酪让Tom去拿，坐标>=50001的奶酪让Jerry去拿。

具体实现时，可以设置一个time值，然后遍历数组。判断每一块奶酪的坐标范围，根据坐标判断应该让谁拿，再计算拿到这个奶酪需要多长时间，如果时间大于time，则用这个值替换掉time的值。

用这种方法，遍历整个数组后的time值即为 Tom 和 Jerry 拿到所有奶酪所用的最短时间。

时间复杂度：O(n)

空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧>>