题解：AT_arc219_c [ARC219C] Traveling Door-to-Door Salesman (Elevator)

DrDuck · 2026-05-13 20:24:20 · 题解

赛时分类讨论分错死活不对，赛后补题光速过题，还好 unr 不然掉分了。

由于坐电梯没有花费，我们可以任意安排访问某行的顺序。

对于每一行而言，我们有三种方式把这一行所有门都访问一遍：

• 从第 1 列开始一路走到底走到第 W 列，或者从第 W 列开始一路走到底走到第 1 列。
• 从第 1 列开始，走到离第 1 列最远的门然后折返回到第 1 列。
• 从第 1 列开始，走到某个门然后回头，等下一次某个时间走到第 W 列之后，把剩下没走的门全部走一遍，然后回到第 W 列。

我们注意到这样一件事情：只要我们在某一行进行了第一种访问方式，我们就可以在其它任意行使用第三种访问方式。

因此我们可以对于是否使用第一种访问方式分类讨论。

• 如果我们不使用，那么我们对于每一行都得使用第二种访问方式。
• 反之我们设 f_{i,0} 为考虑前 i 行，前 i 行没有进行过第一次操作的最小代价，f_{i,1} 为考虑前 i 行，前 i 行进行过奇数次第一次操作的最小代价，f_{i,2} 为考虑前 i 行，前 i 行进行过偶数次第一次操作的最小代价。转移的时候对于每一行枚举一个断点，取代价最小的断点即可。

需要对所有点离散化并排序，时间复杂度 O(N \log N)。

:::success[CODE]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e+5 + 5, inf = 1e17;
int n, NOI, IOI, m;
int b[maxn], f[maxn][3];
vector<int> v[maxn];
struct V {
    int x, y;
}a[maxn];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> NOI >> IOI;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        b[++m] = a[i].x;
    }
    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    for (int i = 1; i <= n; i++) {
        a[i].x = lower_bound(b + 1, b + m + 1, a[i].x) - b;
        v[a[i].x].push_back(a[i].y);
    }
    f[0][1] = f[0][2] = inf;
    int CZR = 0;
    for (int i = 1; i <= m; i++) {
        sort(v[i].begin(), v[i].end());
        int res = min(v[i].back() - 1, IOI - v[i][0]);
        int o = v[i].back() - 1;
        for (int j = 1; j < (int)v[i].size(); j++) {
            res = min(res, v[i][j - 1] - 1 - v[i][j] + IOI);
        }
        res *= 2;
        o *= 2;
        CZR += o;
        f[i][0] = f[i - 1][0] + res;
        f[i][1] = min(min(f[i - 1][0], f[i - 1][2]) + IOI - 1, f[i - 1][1] + res);
        f[i][2] = min(f[i - 1][2] + res, f[i - 1][1] + IOI - 1);
    }
    cout << min({CZR, f[m][2], f[m][1] + IOI - 1});
    return 0;
}

:::