P4703 马拉松（基础）

解题思路

贝茜要按顺序经过 N 个检查点，路线像城市的街道一样横平竖直，所以两点之间要走曼哈顿距离：|x1-x2| + |y1-y2|，也就是先横着走再竖着走。她可以跳过中间某一个检查点（起点和终点不能跳），想让总路程最短。下面分四步实现。

**第一步，算总路程。**先不跳过任何点，把相邻两个点的曼哈顿距离累加起来，得到 total。这一步用一个循环，从第 1 个点走到第 n-1 个点，把每段距离加起来。

**第二步，算节省量。**如果跳过第 i 个点，原来要走"i-1 到 i"和"i 到 i+1"这两段，现在直接走"i-1 到 i+1"这一段。省下来的路程 = 原来两段之和 - 新的一段。这段路的长度用绝对值算：差值为负就取相反数。

**第三步，找最大节省。**对每个中间点 i（从 1 到 n-2）都算一遍节省量，记录最大值 maxSaved。如果跳过某点反而更远，节省量是负数，但负数不会成为最大值，所以不会选它。

**第四步，得答案。**最终答案 = total - maxSaved，输出。

举个例子：4 个检查点 (0,0)、(8,3)、(11,-1)、(10,0)。不跳总路程 = 11 + 7 + 2 = 20。跳过第 2 个点 (8,3)，节省 = (11+7) - (|11-0|+|-1-0|) = 18 - 12 = 6，总路程变成 14，这就是最短的。

边界情况：N 至少是 3（要有中间点可跳）；坐标可能很大，距离加起来可能超过 int，所以要开 long long 数组。

参考代码

// 马拉松：曼哈顿距离，跳过一个中间检查点使总路程最短
#include <iostream>
using namespace std;

long long coordX[100005], coordY[100005]; // 存 N 个检查点坐标，N 可达 10 万

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> coordX[i] >> coordY[i];
    // 先算不跳过时的总路程
    long long total = 0;
    for (int i = 1; i < n; i++) {
        long long dx = coordX[i] - coordX[i - 1];
        if (dx < 0) dx = -dx;
        long long dy = coordY[i] - coordY[i - 1];
        if (dy < 0) dy = -dy;
        total += dx + dy;
    }
    // 对每个中间检查点 i，计算跳过后能省下的路程，找最大值
    long long maxSaved = 0;
    for (int i = 1; i + 1 < n; i++) {
        long long dxPrev = coordX[i] - coordX[i - 1], dyPrev = coordY[i] - coordY[i - 1];
        long long dxNext = coordX[i + 1] - coordX[i], dyNext = coordY[i + 1] - coordY[i];
        long long dxSkip = coordX[i + 1] - coordX[i - 1], dySkip = coordY[i + 1] - coordY[i - 1];
        if (dxPrev < 0) dxPrev = -dxPrev;
        if (dyPrev < 0) dyPrev = -dyPrev;
        if (dxNext < 0) dxNext = -dxNext;
        if (dyNext < 0) dyNext = -dyNext;
        if (dxSkip < 0) dxSkip = -dxSkip;
        if (dySkip < 0) dySkip = -dySkip;
        long long saved = (dxPrev + dyPrev) + (dxNext + dyNext) - (dxSkip + dySkip);
        if (saved > maxSaved) maxSaved = saved;
    }
    cout << total - maxSaved << endl;
    return 0;
}

复杂度分析

先一遍循环算总路程，再一遍循环找最大节省，各循环 N 次，时间复杂度 O(N)。即使 N 大到 10 万也能轻松跑完。空间上只存 N 个点的坐标，O(N)。