专栏文章

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

NN1tr0us_Acid
P13993题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minze16v
此快照首次捕获于
2025/12/02 10:50
3 个月前
此快照最后确认于
2025/12/02 10:50
3 个月前
查看原文
贪心题。

Solution\texttt{Solution}

容易发现，我们在每一层只会踩两个格子，而那么我们只需要最小化这两个格子的和就行了。
我们在第 xx 层寻找的位置一共有 len=min⁡(m,y+kx)−max⁡(1,y−kx)len=\min(m, y+k_x)-\max(1,y-k_x) 个，其实每一层的和可以转化为，求在 11 到 mm 中选择 lenlen 个数，这 lenlen 个数选两个数的和。那么很明显的，这 lenlen 个数必然是 11 到 lenlen。那么我们必然会踩 lenlen 这个数。那么想要最小化这一层的和，就得让从上一层下来时踩到的格子的值最小，那么直接放 11 就行了，每一层的贡献的最小值即为 len+1len+1。
不难发现，我们现在只需要最小化每一层的 lenlen 即可。不妨想想，如果我们每一次下到某一层，都会在这一层的第 11 个或者第 mm 个位置，那么 lenlen 一定最小，这里请读者想想为什么。
所以我们可以通过贪心的摆放当前层的 lenlen 这个数的位置，来控制下一层的初始位置，理由就是这一层会瞬移到的位置上的数一定是 lenlen。
那么贪心就很显然了，这个机器人按这样走就可以使答案最小：
  1. 当前位置是 11，那么如果可以瞬移到第 mm 个位置，瞬移之，否则移到第 22 个位置。
  2. 当前位置是 mm，那么如果可以瞬移到第 11 个位置，瞬移之，否则移到第 m−1m - 1 个位置。
  3. 当前位置是 22，那么如果可以瞬移到第 mm 个位置，瞬移之，否则移到第 11 个位置。
  4. 当前位置是 m−1m - 1，那么如果可以瞬移到第 11 个位置，瞬移之，否则移到第 mm 个位置。
如果你仔细看会发现，上面的 44 条移动规则是可以略作改动的，这里是为了方便理解。

Code\texttt{Code}

按贪心思路模拟即可。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...