【纪中】marathon

2024-01-30 03:48

文章标签 纪中 marathon

本文主要是介绍【纪中】marathon，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

marathon

题目链接：marathon

题目描述

地图上有N 个城市，一只奶牛要从1 号城市开始依次经过N 个城市，最终到达N 号城市。但是这只奶牛觉得这样太无聊了，所以它决定跳过其中的一个城市（但是不能跳过1 号和N 号城市），使得它从1 号城市开始，到达N 号城市所经过的总距离最小。每一个城市都有一个坐标，从城市(x1, y1) 到城市(x2, y2) 的距离为 |x1 - x2| + |y1 - y2|。

输入

第一行一个数N，表示城市个数
接下一行N 行每行两个数x,y，表示每个城市的坐标

输入

第一行一个数N，表示城市个数
接下一行N 行每行两个数x,y，表示每个城市的坐标

输入输出样例

输入

输出

数据范围限制

• 对于40% 的数据，N <= 1000。
• 对于100% 的数据，3 <= N <= 10^5，-103 <= x <= 10^3，-103 <= y <= 10^3。

解题思路

其实就是一道简单的大模拟，点i的价值为abs(x[i]-x[i+1])+abs(y[i]-y[i+1])，用一个maxn储存最大值，再输出去掉这个点后的路程即可。

参考代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,x[100010],y[100010],a[100010];
long long ans,maxn,t;
int main()
{freopen("marathon.in","r",stdin);freopen("marathon.out","w",stdout);cin>>n;for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);for(int i=1;i<n;i++){a[i]=abs(x[i]-x[i+1])+abs(y[i]-y[i+1]);ans+=a[i];}for(int i=1;i<n-1;i++)if(a[i]+a[i+1]-abs(x[i]-x[i+2])-abs(y[i]-y[i+2])>maxn){maxn=a[i]+a[i+1]-abs(x[i]-x[i+2])-abs(y[i]-y[i+2]);t=i;}cout<<ans-maxn<<endl;
}