3. NOIP2015-J-4-推销员 题解

屏幕截图 2025-05-10 151154
屏幕截图 2025-05-10 151213
屏幕截图 2025-05-10 151228
屏幕截图 2025-05-10 151237

思路

60%分数

如果你想不到正解的话,你可以打暴力求解60%的分数 (n \le 1000)的部分。
O(n^2) 的算法枚举每个点的距离,最后取最大值即可。

100%分数

整体思路是贪心。
我们简单的分个类:

  1. 当 3. X = 1 的时候,为了使总值最大,我们可以简单计算一下,得知,去每个地方消耗的疲惫值是距离 * 2 + 推销(往返是两倍)。(记录现在的距离为Max)
  2. X = 2-n 的时候,每次选取推销消耗最大的,如果他的距离比Max大,那么就加上 (距离- Max) * 2 + 推销,并且将Max更新为当前的疲惫值。

时间复杂度: O(n)

%%%大佬

屏幕截图 2025-05-11 184138