CCPC-Wannafly Winter Camp Day4 Div1 - 夺宝奇兵

题目链接：https://zhixincode.com/contest/18/problem/A?problem_id=259

题目描述

wls正在玩一个寻宝游戏。

宝藏一共有 $n$ 种，都藏在一个 $m$ 行 $m$ 列的网格中。

每种宝藏都恰好有两个。

wls只能沿着网格走（上下左右四个方向）。

他想依次获得 $1...n$ 类宝藏，然后再以 $n...1$ 的顺序获得剩下的宝藏。

wls可以从任意点出发。

当wls到达某个宝藏的位置时，他可以选择取或不取这个宝藏。

请问他最少要移动多少距离？

输入描述

第一行两个整数 $n$，$m$。

接下来 $n$ 组，每组两行表示一类宝藏，每行两个整数 $x$，$y$ 表示一个宝藏的坐标。

$1≤n,m≤100000$
$1≤x,y≤m$

输出描述

一行一个整数表示答案。

题解：

将问题转换为两个人同时从第 $1$ 种宝藏出发，沿着 $1~n$ 的顺序拿宝藏。

假设第 $1$ 种宝藏分别为 $1a$ 和 $1b$，第 $2$ 种宝藏也分别为 $2a,2b$，那么只有两种选择 $1a → 2a, 1b → 2b$ 或者 $1a → 2b, 1b → 2a$，选择路程更短的就好了，因为不管当前怎么选择，对之后都没有任何影响。

最后再加个 $na$ 到 $nb$ 之间的路程就好了。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+;

int n,m;

struct P{

    int x,y;

}p[maxn][];

ll dist(P a,P b)

{

    return (ll)abs(a.x-b.x)+abs(a.y-b.y);

}

int main()

{

    cin>>n>>m;

    for(int i=;i<=n;i++)

    {

        scanf("%d%d",&p[i][].x,&p[i][].y);

        scanf("%d%d",&p[i][].x,&p[i][].y);

    }

    ll ans=;

    for(int i=;i<=n;i++)

    {

        ans+=min(dist(p[i-][],p[i][])+dist(p[i-][],p[i][]),dist(p[i-][],p[i][])+dist(p[i-][],p[i][]));

    }

    cout<<ans+dist(p[n][],p[n][])<<endl;

}

巴特西

CCPC-Wannafly Winter Camp Day4 Div1 - 夺宝奇兵 - [简单思维题]

最新文章

热门文章