「JOISC 2017 Day 1」开荒者

单独一个点，假如固定每个操作的数目，则得到的草呈矩形，且形状不会应操作顺序变化而变化。所以最后的结果与操作顺序无关。同时发现当向上、下次数总和一定时，若无上下边界，则草地形状一样。

考虑枚举向上、向下次数和，可以通过差分扫描线的方式维护出草地的形状（由于一个点只会被加入一次，删除一次，所以扫描线点数 \(O(n)\) 级别）。

考虑对于每一行对答案的贡献，设第 \(i\) 每一株草的位置时 \(a1 \dots a_m\) ，则向左向右对答案的贡献为 \(f_i = max(a_1 – 1, c – a_m, max_{i = 1}^{m – 1}(a{i + 1} – a{i})\) ，现在考虑上下的边界，答案为 \(min_{i}(max_{i \leq j \leq i + r – 1} f_j)\) ，可以用单调队列维护。
时间复杂度 \(O(n^3)\) .

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 605;

int R, C, n, lim, m, f[N][3], q[3][N], l[3], r[3];

bool vis[N][N];

set <int> s;

ll ans;

struct Node {
    int x, y;
} a[N], b[N];

bool cmpx_(Node a, Node b) {
    return a.x < b.x;
}

bool cmpy_(Node a, Node b) {
    return a.y < b.y;
}

void solve_(int k) {
    for (int i = 1; i <= n; i++)
        vis[k][i] = vis[k - 1][i];

    if (b[k].y > 0)
        vis[k][b[k].y] = 1;
    else
        vis[k][-b[k].y] = 0;

    f[k][0] = f[k][1] = f[k][2] = 0;

    for (int i = 1, j = 0; i <= n; i++)
        if (vis[k][i]) {
            f[k][2] = C - a[i].y;

            if (j)
                f[k][0] = max(f[k][0], a[i].y - a[j].y - 1);
            else
                f[k][1] = a[i].y - 1;

            j = i;
        }
}

void init_(int d) {
    sort(a + 1, a + n + 1, cmpy_);

    for (int i = 1; i <= n; i++) {
        b[++m] = (Node) {
            a[i].x - d, i
        };
        b[++m] = (Node) {
            a[i].x + 1, -i
        };
    }

    sort(b + 1, b + m + 1, cmpx_);

    for (int i = 1; i < m; i++)
        solve_(i);
}

ll calc_(int d) {
    for (int i = 1; i <= m; i++)
        if (b[i].y > 0)
            b[i].x -= d;

    bool ok = 1;

    while (ok) {
        ok = 0;

        for (int i = 1; i < m; i++)
            if (b[i].x > b[i + 1].x) {
                ok = 1, swap(b[i], b[i + 1]);
                solve_(i), solve_(i + 1);
            }
    }

    ll res = 4e9;

    for (int i = 0; i < 3; i++)
        l[i] = 1, r[i] = 0;

    for (int i = 1, j = 1; ; i++) {
        while (j < m && b[j].x - b[i].x < R) {
            if (b[j].x < b[j + 1].x) {
                for (int k = 0; k < 3; k++) {
                    while (l[k] <= r[k] && f[q[k][r[k]]][k] <= f[j][k])
                        r[k]--;

                    q[k][++r[k]] = j;
                }
            }

            j++;
        }

        if (b[j].x - b[i].x < R)
            break;

        for (int k = 0; k < 3; k++)
            while (l[k] <= r[k] && q[k][l[k]] < i)
                l[k]++;

        res = min(res, max(1ll * f[q[0][l[0]]][0], 1ll * f[q[1][l[1]]][1] + f[q[2][l[2]]][2]));
    }

    return res;
}

int main() {
    scanf("%d%d%d", &R, &C, &n), ans = R + C - 2;

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].x, &a[i].y);

    sort(a + 1, a + n + 1, cmpx_);

    lim = a[1].x - 1 + R - a[n].x;

    for (int i = 1; i < n; i++)
        lim = max(lim, a[i + 1].x - a[i].x - 1);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (a[i].x - 1 + R - a[j].x >= lim)
                s.insert(a[i].x - 1 + R - a[j].x);

            if (a[j].x - a[i].x - 1 >= lim)
                s.insert(a[j].x - a[i].x - 1);
        }

    init_(*s.begin());

    int last = *s.begin();

    for (int x : s) {
        ans = min(ans, x + calc_(x - last)), last = x;

        if (ans <= last)
            break;
    }

    printf("%lld\n", ans);
}