思路
60%分数
如果你想不到正解的话,你可以打暴力求解60%的分数 (n \le 1000)的部分。
用 O(n^2) 的算法枚举每个点的距离,最后取最大值即可。
100%分数
整体思路是贪心。
我们简单的分个类:
- 当 3. X = 1 的时候,为了使总值最大,我们可以简单计算一下,得知,去每个地方消耗的疲惫值是距离 * 2 + 推销(往返是两倍)。(记录现在的距离为Max)
- 当 X = 2-n 的时候,每次选取推销消耗最大的,如果他的距离比Max大,那么就加上 (距离- Max) * 2 + 推销,并且将Max更新为当前的疲惫值。
时间复杂度: O(n)