题解：P13993 【MX-X19-T2】「LAOI-14」SPECIALZ

· · 题解

贪心题。

\texttt{Solution}

容易发现，我们在每一层只会踩两个格子，而那么我们只需要最小化这两个格子的和就行了。

我们在第 x 层寻找的位置一共有 len=\min(m, y+k_x)-\max(1,y-k_x) 个，其实每一层的和可以转化为，求在 1 到 m 中选择 len 个数，这 len 个数选两个数的和。那么很明显的，这 len 个数必然是 1 到 len。那么我们必然会踩 len 这个数。那么想要最小化这一层的和，就得让从上一层下来时踩到的格子的值最小，那么直接放 1 就行了，每一层的贡献的最小值即为 len+1。

不难发现，我们现在只需要最小化每一层的 len 即可。不妨想想，如果我们每一次下到某一层，都会在这一层的第 1 个或者第 m 个位置，那么 len 一定最小，这里请读者想想为什么。

所以我们可以通过贪心的摆放当前层的 len 这个数的位置，来控制下一层的初始位置，理由就是这一层会瞬移到的位置上的数一定是 len。

那么贪心就很显然了，这个机器人按这样走就可以使答案最小：

  1. 当前位置是 1，那么如果可以瞬移到第 m 个位置，瞬移之，否则移到第 2 个位置。
  2. 当前位置是 m，那么如果可以瞬移到第 1 个位置，瞬移之，否则移到第 m - 1 个位置。
  3. 当前位置是 2，那么如果可以瞬移到第 m 个位置，瞬移之，否则移到第 1 个位置。
  4. 当前位置是 m - 1，那么如果可以瞬移到第 1 个位置，瞬移之，否则移到第 m 个位置。

如果你仔细看会发现，上面的 4 条移动规则是可以略作改动的，这里是为了方便理解。

\texttt{Code}

按贪心思路模拟即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n, m;
int ans;
int now = 1;
signed main(void) {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    ans = n;
    for (int i = 1; i <= n; i ++) {
        int k;
        cin >> k;
        int l = now - k, r = now + k;
        l = max(l, 1ll), r = min(r, m);
        int len = r - l + 1;
        len = min(len, m);
        ans += len;
        if(len == m) {
            if(now == m) now = 1;
            else now = m;
        }
        else {
            if(now == 1) now = 2;
            else if(now == 2) now = 1;
            else if(now == m) now = m - 1;
            else if(now == m - 1) now = m;
        }
    }
    cout << ans;
    return 0;
}