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

KirinRYato · 2025-09-07 00:28:12 · 题解

本题的关键是尽量让每一次瞬移后最小，因为可以把操作2到达的位置设为1，每一行只能1~m每个数填一次，又因为操作1的瞬移有范围限制，所以只要让大的数尽量在位移的范围外，也就是让每次的min(y+kx,m)-max(y-kx,1)最小。只要控制机器人每次都在最左边或最右边的两个位置就能保证每次能瞬移到的范围最小，使用贪心就能解决。

下面是AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 500001;
long long n, m, k[N], num = 1, ny = 1, j = 1; // ny记录当前位置，num记录总数
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> k[i];
    for (int i = 1; i <= n; i++)
    {
        num += min(ny + k[i], m) - max(ny - k[i], j) + 1; // max(ny - k[i], 1)会出错
        if (i != n)
            num++;
        if (ny == m || ny == m - 1) // 如果机器人在右半边
        {
            if (ny - k[i] <= 1)
                ny = 1;
            else if (ny == m) // 到不了最左边
                ny = m - 1;
            else
                ny = m;
        }
        else // 如果机器人在左半边
        {
            if (ny + k[i] >= m)
                ny = m;
            else if (ny == 1) // 到不了最右边
                ny = 2;
            else
                ny = 1;
        }
    }
    cout << num;
    return 0;
}