49.吃奶酪

题目概述

题目详情(点我)

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

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

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

题解

解题方法

• 比较法, 对称思想

算法知识

• 贪心算法

  • 时间复杂度: n
  • 空间复杂度: 1

解题思路

审题

• int n : 奶酪的块数
• int[] nums : 奶酪对应的坐标位置
• 坐标+1 耗时1秒
• 可以一次拿完坐标上的多块奶酪
• Tom和Jerry分别在1和100000两个点上

题目要求

• 获取拿到所有奶酪的最短时间

思路

• 既然要最短时间, 那么就必须得以5000为分界线, 5000及之前的奶酪由Tom拿, 5000之后的奶酪有Jerry拿, 这样就能保证所花时间最短。

• 利用对称思想,
  Jerry拿到奶酪的时间为: 100000-nums[i];
  Tom拿到奶酪的时间为: nums[i]-1;

步骤

1. 定义变量int result, time分别用来存储最终时间和拿nums[i]奶酪需要的时间, 初始化为0

2. 循环遍历nums, 获取最终需要的时间result

   • 如果奶酪的坐标在 50000及之前, 则让tom去拿, 并计算需要花的时间time (nums[i]-1), 将time和result进行比较, 让result的值为两者中最大的值。
   • 如果奶酪的坐标在 50000之后, 则让Jerry去拿, 并计算需要花的时间time (100000-nums[i]), 将time和result进行比较, 让result的值为两者中的最大值。
3. 返回result