1902.马拉松(数学思维)
本文最后更新于 761 天前,其中的信息可能已经有所发展或是发生改变。

1902.马拉松(数学思维)

原题链接

描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据范围
3≤N≤105,
−1000≤x,y≤1000
输入样例:

4
0 0
8 3
11 -1
10 0

输出样例:

14

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

分析

  • 假设不略过检查点,跑完全程需要的距离为sum取连续的一组检查点记为A,B,C
  • AB两个检查点的距离为d1,BC两个检查点的距离为d2,AC两个检查点的距离为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];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&a[i].x,&a[i].y);
        if(i>2){  //去除掉首尾的点,从第3个点开始判断,此时第i个点即为一组连续的A,B,C点中的C点
            // 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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇