AcWing 1902. 马拉松

本文主要是介绍AcWing 1902. 马拉松，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

每次路程改变只对前后两点间距离有影响，因此每次都判断当前三个点之间的距离之和与去掉中间点的距离哪个更优即可，最后取最大值作为结果输出。

#include<iostream>
#include<cmath>

using namespace std;

const int N = 100010;

int x[N], y[N];

int dis(int a,int b)
{
    return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}

int main(){
    int n, s=0, mx=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for(int i=2;i<=n;i++)
        s+=dis(i-1, i);
    for(int i=2;i<=n-1;i++)
        mx = max(mx, dis(i-1, i) + dis(i+1, i) - dis(i-1, i+1));
    cout<<s-mx;
    return 0;
}

这篇关于AcWing 1902. 马拉松的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！