1902-马拉松数学思维

1902.马拉松(数学思维)

原题链接

描述

农夫约翰对他的奶牛们的健康状况并不满意，于是给他的奶牛们报名了各种健身活动。

他最喜欢的奶牛贝茜被报名参加了一个跑步班。

在那里，她有望在一场马拉松比赛中穿越约翰农场所在的城市的市中心。

马拉松线路由 N 个检查点（编号 1∼N）指定。

检查点 1 是起点，检查点 N 是终点，贝茜要按顺序经过每个检查点。

但是贝茜十分懒惰，所以她决定跳过其中一个检查点，以缩短她的整个行程。

但是，她不能跳过检查点 1 和检查点 N，因为这太容易被人发现了。

在她可以跳过一个检查点的情况下，请确定她需要行进的最短距离。

由于该路线设置在市中心，街道呈网格状交错，因此两个检查站点 (x1,y1) 与 (x2,y2) 之间的距离应该为 |x1−x2|+|y1−y2|。

输入格式 第一行包含整数 N。

接下来 N 行，每行包含两个整数 x,y，表示一个检查点的横纵坐标。检查点按 1∼N 的顺序给出。

请注意，比赛线路可能存在交叉，在同一物理位置出现多个检查点。

当贝茜跳过这样一个检查点时，她只跳过其中一个检查点，而不是跳过这个位置上的所有检查点。

输出格式 输出贝茜可以跳过一个检查点的情况下，需要行进的最短距离。

数据范围 3≤N≤10^5, −1000≤x,y≤1000

输入样例：

4
0 0
8 3
11 -1
10 0

输出样例：

14

样例解释 最佳方案是跳过 (8,3)。

分析 ：

• 假设不跳过检查点，跑完全程需要的距离为sum，取连续的一组检查点记为A,B,C
  • 设A和B两个检查点的距离为d1，B和C两个检查点的距离为d2，A和C两个检查点的距离为d3
  • 如果不经过检查点B可以使得到达目标的路径最短，即使得sum-d1-d2+d3最小
  • 必须满足：在任意连续的一组检查点A,B,C中，-d1-d2+d3的值最小

代码 ：

#include <bits/stdc++.h>
using namespace std;

long long sum;

const int N=1e6+10;

struct pp{
    int x,y;  //存储点的坐标
};

int n,road=1e6;  //road用来维护d3-d1-d2的最小值

int past,now;  //past为d1+d2  now为d3

pp a[N];

#include <stdio.h>
#include <stdlib.h>

struct point {
    int x, y;
};

int main() {
    int n;
    struct point a[1000];
    long long road = 1000000000000000000LL;
    long long past = 0, now = 0, sum = 0;

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].x, &a[i].y);
        if (i > 2) {
            // l暂时记录d1+d2
            int l = abs(a[i-1].x - a[i-2].x) + abs(a[i-1].y - a[i-2].y) + abs(a[i].x - a[i-1].x) + abs(a[i].y - a[i-1].y);
            int pos = abs(a[i].x - a[i-2].x) + abs(a[i].y - a[i-2].y);  // pos暂时记录d3
            if (pos - l < road) {  // pos-l 即为 -d1-d2+d3 的值，判断是否更新road
                road = pos - l;
                past = l;
                now = pos;
            }
        }
        if (i > 1) {
            sum += abs(a[i].x - a[i-1].x) + abs(a[i].y - a[i-1].y);  // 记录全程的长度
        }
    }
    printf("%lld", sum - past + now);  // sum-d1-d2+d3
    return 0;
}