「JOISC 2017 Day 1」开荒者

发表于
https://loj.ac/problem/2390

题目链接

「JOISC 2017 Day 1」开荒者

做法

单独一个点，假如固定每个操作的数目，则得到的草呈矩形，且形状不会应操作顺序变化而变化。所以最后的结果与操作顺序无关。同时发现当向上、下次数总和一定时，若无上下边界，则草地形状一样。
考虑枚举向上、向下次数，可以通过差分扫描线的方式维护出草地的形状（由于一个点只会被加入一次，删除一次，所以扫描线点数 $ O(n) $ 级别）。
考虑对于每一行对答案的贡献，设第 $ i $ 每一株草的位置时 $ a_1 \dots a_m $ ，则向左向右对答案的贡献为 $ f_i = \max(a_1 - 1, c - a_n, \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) $ ，常数略大。 

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 910;
int r, c, n, smn, wmn, swmn; ll ans;
pii a[N];
set<int> s, w, All;
pii b[N]; int tot, len[N], ex[N][N], lmt[N][3]; ll sum[N];

template<typename T> void gi(T &x) {
	x = 0; register char c = getchar(); for(; c < '0' && c > '9'; c = getchar());
	for(; c >= '0' && c <= '9'; x = x * 10ll + (c ^ 48), c = getchar());
}
inline bool cmp(const pii &x, const pii &y) { return x.snd < y.snd; }
void calc(int x) {
	int lst = 0, mx = 0;
	rep(i, 1, n) if(ex[x][i]) {
		if(!lst) lmt[x][0] = a[i].snd - 1;
		else mx = max(mx, a[i].snd - a[lst].snd - 1);
		lst = i;
	}
	lmt[x][1] = c - a[lst].snd, lmt[x][2] = mx;
}
void init(int x) {
	sort(a + 1, a + n + 1, cmp);
	rep(i, 1, n) b[++tot] = mp(a[i].fst - x, -i), b[++tot] = mp(a[i].fst + 1, i);
	sort(b + 1, b + tot + 1);
	rep(i, 1, tot - 1) {
		len[i] = b[i + 1].fst - b[i].fst; rep(j, 1, n) ex[i][j] = ex[i - 1][j];
		b[i].snd < 0 ? (ex[i][-b[i].snd] = 1) : (ex[i][b[i].snd] = 0);
		calc(i);
	}
}
void Swap(int x, int y) {
	swap(b[x], b[y]);
	rep(i, x, y) {
		rep(j, 1, n) ex[i][j] = ex[i - 1][j];
		b[i].snd < 0 ? (ex[i][-b[i].snd] = 1) : (ex[i][b[i].snd] = 0);
		calc(i);
	}
}
ll solve(int x) {
	rep(i, 1, tot) if(b[i].snd < 0) b[i].fst -= x;
	bool flag = 1;
	for(; flag;) { flag = 0; rep(i, 1, tot - 1) if(b[i + 1] < b[i]) Swap(i, i + 1), flag = 1; }
	rep(i, 1, tot - 1) len[i] = b[i + 1].fst - b[i].fst;
	rep(i, 2, tot) sum[i] = sum[i - 1] + len[i - 1];
	deque<int> q[3]; int res = c + c - 2;
	for(int i = 1, j = 1; j <= tot; i++) {
		for(; j < tot && sum[j] - sum[i] < r; ++j)
			if(len[j]) {
				rep(k, 0, 2) {
					for(; !q[k].empty() && lmt[q[k].back()][k] <= lmt[j][k]; q[k].pop_back());
					q[k].push_back(j);
				}
			}
		if(sum[j] - sum[i] < r) break;
		int x = lmt[q[0].front()][0], y = lmt[q[1].front()][1], z = lmt[q[2].front()][2];
		res = min(res, max(x + y, z));
		rep(k, 0, 2) if(q[k].front() == i) q[k].pop_front();
	}
	return res;
}
int main() {
	gi(r), gi(c), gi(n), ans = r + c - 2;
	rep(i, 1, n) gi(a[i].fst), gi(a[i].snd); sort(a + 1, a + n + 1);
	smn = a[1].fst - 1, wmn = r - a[n].fst, swmn = smn + wmn;
	rep(i, 1, n - 1) swmn = max(swmn, a[i + 1].fst - a[i].fst - 1);
	rep(i, 1, n) {
		s.insert(a[i].fst - 1), w.insert(r - a[i].fst);
		rep(j, i, n) if(a[j].fst - a[i].fst - 1 >= swmn) All.insert(a[j].fst - a[i].fst - 1);
	}
	for(auto i : s) for(auto j : w) if(i + j >= swmn) All.insert(i + j);
	init(*All.begin()); int lst = *All.begin();
	for(auto i : All) ans = min(ans, i + solve(i - lst)), lst = i;
	printf("%lld\n", ans);
	return 0;
}