ζ

CF1716C-Robot in a Hallway

    题解

题目大意：给出一个2行n列的网格图。最开始的时刻为0，用一个单位时间可以从一个网格可以移动到任意与其有公共边的网格。但第i行第j列的网格上有数a[i][j]，当且仅当当前时刻严格大于这个数时，才能移动到这个网格上。问最少需要多少单位时间才能在不访问重复网格的前提下遍历所有网格。

因为只有两行，且不允许重复访问格子，走法其实非常有限。具体可以总结为：先用蛇形走法遍历一些格子，然后再从某个格子开始，先走到网格列的尽头，换行，再走回来（称：回旋）。

从起点通过蛇形走法到一个格子的路径是固定的，从一个格子开始回旋直到遍历完所有格子的方法也是固定的。现在的问题就是：应该通过蛇形走法走到到哪个格子再开始遍历？

通过蛇形走法到各个格子再暴力判断此时开始回旋的最终耗时显然不行。注意到：如果不考虑前面已经累计的时间，或累计的时间不足以满足在路上不被阻塞，走到(x, n)的时刻是

max(a[x][i]+1+n−i)(i∈[y,n])max(a[x][i]+1+n-i)(i \in [y,n])

如果在到达(x, y)时已经积累了较多时间，在从(x, y)走到(x, n)的期间不被堵塞。记到达(x, y)的时刻为cur，则走到(x, n)的时刻是

cur+(n−y)cur+(n-y)

因此从走到(x, n)的最早时刻是

max(max(a[x][i]+1+n−i)(i∈[y,n]),cur+(n−y))max(max(a[x][i]+1+n-i)(i \in [y,n]),cur+(n-y))

之后来到(x^1, n)，换行往回走。设终点为(x^1, t)。同样，如果不考虑前面已经累计的时间，走到(x^1, t)的时刻是

max(a[x⊕1][i]+1+i−t)(i∈[t,n])max(a[x \oplus 1][i]+1+i-t)(i \in [t,n])

同理，如果前面积累的时间能保证不被阻塞，记到达(x^1, n)的时刻为cur，走到(x^1, t)的时刻是

cur+(n−t)cur+(n-t)

因此从走到(x^1, t)的最早时刻是

max(max(a[x⊕1][i]+1+i−t)(i∈[t,n]),cur+(n−t))max(max(a[x \oplus 1][i]+1+i-t)(i \in [t,n]),cur+(n-t))

观察两行的式子，发现只要分别维护两行各个后缀上a[x][y] + y和a[x][y] - y的最大值，就能比较快速地得到答案了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[2][200005], sp[2][200005], sm[2][200005];
bool vis[2][200005];
signed main()
{
    int n, _;
    scanf("%lld", &_);
    while (_--)
    {
        scanf("%lld", &n);
        for (int o = 0; o < 2; o++)
        {
            for (int i = 1; i <= n; i++)
                scanf("%lld", &a[o][i]);
        }
        a[0][1] = -1;
        for (int o = 0; o < 2; o++)
        {
            sp[o][n] = a[o][n] + n;
            for (int i = n - 1; i; i--)
                sp[o][i] = max(a[o][i] + i, sp[o][i + 1]);
        }
        for (int o = 0; o < 2; o++)
        {
            sm[o][n] = a[o][n] - n;
            for (int i = n - 1; i; i--)
                sm[o][i] = max(a[o][i] - i, sm[o][i + 1]);
        }
        int res = 1e18, now = 0, x = 0, y = 1;
        for (int o = 0; o < 2; o++)
        {
            for (int i = 1; i <= n; i++)
                vis[o][i] = 0;
        }
        vis[0][1] = 1;
        for (int sum = 1;; sum++)
        {
            if (sum == (n << 1))
            {
                res = min(res, now);
                break;
            }
            int cur = now + (n - y);
            if (y < n)
                cur = max(cur, sm[x][y] + 1 + n);

            cur = max(cur + 1, a[x ^ 1][n] + 1);

            int t = y;
            if (vis[x ^ 1][y])
                t++;

            cur = max(cur + n - t, sp[x ^ 1][t] + 1 - t);
            res = min(cur, res);

            if (!vis[x ^ 1][y])
                x ^= 1;
            else
                y++;
            vis[x][y] = 1;
            now = max(now + 1, a[x][y] + 1);
        }
        printf("%lld\n", res);
    }
    return 0;
}
页阅读量:  ・  站访问量:  ・  站访客数: