1902.马拉松(数学思维)
1902.马拉松(数学思维)
浪漫主义狗
发布于 2022-07-11 08:47:53
发布于 2022-07-11 08:47:53
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 - 设
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];
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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-6-15 9，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录