c++：接苹果【求解】

Question

描述

童童设计了一款接苹果的电脑桌面游戏。有n个苹果从屏幕顶部的某一处垂直往下掉，一直掉到屏幕底部，在前一个苹果到达屏幕底部后，下一个苹果才开始往下掉。当苹果掉到屏幕底部时，如果篮子正好在相同的地方，则认为苹果被成功接起。游戏的目标是用最少的移动步数接起掉下来的苹果。游戏舞台的中心点坐标值为(0,0)，第一个数代表x坐标，第二个数代表y坐标。x坐标的最小值位于舞台最左端为-240，最大值位于舞台的最右端为240。y坐标的最小值位于舞台最下端为-180，最大值位于舞台最上端为180。篮子如果向左移动，x坐标值会减少，向右移动x坐标值则会增加。篮子的初始位置在(x1,-180)，苹果都从坐标(x2,180)往下掉。

编写一个程序，求出接起所有苹果时，篮子最少的移动步数。

输入描述

共三行。
第一行，一个整数x1（-240≤x1≤240）,表示篮子的初始x坐标。
第二行，一个整数n（1≤n≤106），表示苹果的个数。
第三行，n个整数x2（-240≤x2≤240），表示按照苹果下落顺序描述每个苹果的x坐标，数与数之间以一个空格隔开。

输出描述

一行，一个整数，表示接起所有苹果，篮子最少的移动步数。

样例输入 1

8
4
0 -1 -3 10

样例输出 1

24

提示

样例说明：
篮子的初始位置(8,-180)，一共掉落4个苹果，掉落位置的x坐标分别为0 -1 -3 10，篮子接住4个苹果分别需要移动的步数为8 1 2 13，一共需要移动的步数就是8+1+2+13=24。

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

思路：假设篮子每次移动到苹果处，到下一个苹果时篮子离开此处，再到下一个苹果处。对于从第i个到第i+1个苹果的移动，我们可以将篮子处于i+1时与i的连线上下分别与y=-180和y=180切割，而篮子每次只能从i+1沿着y=-180或y=180到达i，这就是一个模拟问题。 算法1 (暴力模拟) $O(n)$ 按照思路模拟即可，注意细节。 时间复杂度 模拟的次数是n-1次，每次需要计算篮子移动的最小路程，故时间复杂度为O(n)。 Python 代码 C++ 代码 算法2 (优化算法1) $O(n)$ 模拟的过程中有很多重复的计算，优化方法有两种：

• 缓存前面的结果，这样每一次要移动到某点时，可以直接使用前面的结果，不必重新计算。
• 通过递推公式计算结果。 在算法1中我们使用的是第一种，时间复杂度为O(n2)。在算法2中，我们考虑使用动态规划来递推计算结果。 设S(i,j)为篮子走到从第i个苹果到第j个苹果的最少移动距离。则必然有 $$\begin{cases}S(i,i+1)=abs(AP_{i+1})\ S(i,j)=min(\max(S(k,j-1),AB_{ki}))&(k \in [i,j-1])\end{cases}$$ 其中AP、AB为向量表示，S(i,j)是三角形OAP、OAB的面积。 时间复杂度 在缓存了结果后，每次计算都只需要O(1)时间，一共计算n-1轮，故时间复杂度为O(n)。 Python 代码 C++ 代码