D. Treasure Hunting （ 思维题 ， 贪心）

传送门

题意： 在一个 n * m 的地图里，有 k 个宝藏，你的起点在 （1， 1）， 每次你能 向下向右向左移动（只要在地图里）；

　　     现在，有 q 个安全的列， 你只有在这些列上面，你才能向下走。 问你收集所有宝藏，需要走的最少步数

解： 首先，我们对每一行 维护数组 L, R，分别代表 这一行的所有宝藏中，最左的那个和最右的那个的 纵坐标

　　然后 维护两个值  ansl， ansr 分别代表你处理完前 i 行所有的宝藏都拿完了之后；

　　停在 L[ i ]， 和停在 R[ i ]处的最小步数；

　　那么你更新 ansl, ansr 各有四种情况； （ 代码有提到，详见代码）

　　然后处理完N行后， 去 ansl, ansr 较小的那个，就是所有横向需要走的最小步数。

　　然后纵向的话，你走的步数就是 所有宝藏中最大的 x - 1 步；

　　然后相加就是答案了。

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#define LL long long

#define ULL unsigned long long

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define dep(i,j,k) for(int i=k;i>=j;i--)

#define INF 0x3f3f3f3f3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define make(i,j) make_pair(i,j)

#define pb push_back

#define Pi acos(-1.0)

using namespace std;

const int N = 2e5 + ;

LL l[N], r[N], s[N];

int main() {

    int n, m, k, q;

    while(~scanf("%d %d %d %d", &n, &m, &k, &q)) {

        rep(i, , n) l[i] = INF, r[i] = ;

        LL Y = ;

        rep(i, , k) {

            LL x, y;

            scanf("%lld %lld", &x, &y);

            Y = max(Y, x);

            l[x] = min(l[x], y);

            r[x] = max(r[x], y);

        }

        rep(i, , q) scanf("%lld", &s[i]);

        sort(s + , s +  + q);

        LL ansl, ansr;

        LL L = l[], R = r[];

        if(r[] == ) ansl = , ansr = , L = R = ;

        else ansl = r[] -  + r[] - l[], ansr = r[] - ;

        rep(i, , n) if(r[i]) {

            int indexl = lower_bound(s + , s +  + q, L) - s;

            int indexr = lower_bound(s + , s +  + q, R) - s;

            int Ll, Lr, Rl, Rr;  Ll = Lr = Rl = Rr = INF;

            if(indexl <= q) Lr = s[indexl]; if(indexl > ) Ll = s[indexl - ];

            if(indexr <= q) Rr = s[indexr]; if(indexr > ) Rl = s[indexr - ];

            LL nowL = INF, nowR = INF;

            nowL = min(nowL, ansl + abs(L - Ll) + abs(Ll - r[i]) + abs(r[i] - l[i])); ///L -> Ll -> r[i] -> l[i]

            nowL = min(nowL, ansl + abs(L - Lr) + abs(Lr - r[i]) + abs(r[i] - l[i])); ///L -> Lr -> r[i] -> l[i]

            nowL = min(nowL, ansr + abs(R - Rl) + abs(Rl - r[i]) + abs(r[i] - l[i])); ///R -> Rl -> r[i] -> l[i]

            nowL = min(nowL, ansr + abs(R - Rr) + abs(Rr - r[i]) + abs(r[i] - l[i])); ///R -> Rr -> r[i] -> l[i]

            nowR = min(nowR, ansl + abs(L - Ll) + abs(Ll - l[i]) + abs(l[i] - r[i])); ///L -> Ll -> l[i] -> r[i]

            nowR = min(nowR, ansl + abs(L - Lr) + abs(Lr - l[i]) + abs(l[i] - r[i])); ///L -> Lr -> l[i] -> r[i]

            nowR = min(nowR, ansr + abs(R - Rl) + abs(Rl - l[i]) + abs(l[i] - r[i])); ///R -> Rl -> l[i] -> r[i]

            nowR = min(nowR, ansr + abs(R - Rr) + abs(Rr - l[i]) + abs(l[i] - r[i])); ///R -> Rr -> l[i] -> r[i]

            ansl = nowL, ansr = nowR; L = l[i], R = r[i];

        }

        printf("%lld\n", min(ansl, ansr) + Y - );

    }

    return ;

}