赶牛入圈

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含 $C$ 单位的三叶草，来当做它们的下午茶。

畜栏的边缘必须与 $X，Y$ 轴平行。

约翰的土地里一共包含 $N$ 单位的三叶草，每单位三叶草位于一个 $1×1$ 的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的 $X,Y$ 坐标都为整数，范围在 $1$ 到 $10000$ 以内。

多个单位的三叶草可能会位于同一个 $1×1$ 的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下，能包含至少 $C$ 单位面积三叶草的情况下，畜栏的最小边长是多少。

输入格式

第一行输入两个整数 $C$ 和 $N$。

接下来 $N$ 行，每行输入两个整数 $X$ 和 $Y$，代表三叶草所在的区域的 $X,Y$ 坐标。

同一行数据用空格隔开。

输出格式

输出一个整数，代表畜栏的最小边长。

数据范围

$1≤C≤500$,
$C≤N≤500$

输入样例：

1
2
3
4
5
3 4
1 2
2 1
4 1
5 2

输出样例：

1
4

题目解析

激光炸弹 同类型题，暴力前加个离散化即可

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
#include <cstdio>
#include <iostream>
#include <algorithm>

const int N = 1005;
int arr[N * 2], cur[N * 2], Map[N][N], sum[N][N];
struct Node {
	int x, y;
} point[N];

int c;

//注意 这里判断是否超过C的时候不能再放到离散化数组里面算 要放到原数据里判断
bool check(int len, int n, int m) {
	for (int x1 = 1, x2 = 1; x2 <= n; x2++) {
	    while(cur[x2] - cur[x1] + 1 > len) x1++;
		for (int y1 = 1, y2 = 1; y2 <= m; y2++) {
		    while(cur[y2] - cur[y1] + 1 > len) y1++;
			if(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] >= c) return true;
		}
	} return false;
}

int main() {
	int n;
	scanf("%d %d", &c, &n);
	int k = 0;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		arr[++k] = x; arr[++k] = y;
		point[i].x = x; point[i].y = y;
	}
	
	std::sort(arr + 1, arr + 1 + k);
	
	int t = 0;
	cur[++t] = arr[1];
	for (int i = 2; i <= k; i++) {
		if(arr[i] != arr[i - 1]) cur[++t] = arr[i];
	}
	
	int xmaxx = 0, ymaxx = 0;
	for (int i = 1; i <= n; i++) {
		int l = 1, r = t;
		while(l < r) {
			int mid = (l + r + 1) >> 1;
			if(point[i].x == cur[mid]) { point[i].x = mid; break; }
			else if(point[i].x > cur[mid]) l = mid;
			else r = mid - 1;
		} xmaxx = std::max(xmaxx, point[i].x);
		
		l = 1, r = t;
		while(l < r) {
			int mid = (l + r + 1) >> 1;
			if(point[i].y == cur[mid]) { point[i].y = mid; break; }
			else if(point[i].y > cur[mid]) l = mid;
			else r = mid - 1;
		} ymaxx = std::max(ymaxx, point[i].y);
	}//离散化
	
	for (int i = 1; i <= n; i++) Map[point[i].x][point[i].y]++;
	
	int m = std::max(ymaxx, xmaxx);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + Map[i][j];
		}
	}
		
	int l = 1, r = 10000;
	while(l < r) {
		int mid = (l + r) >> 1;
		if(check(mid, t, t)) r = mid;
		else l = mid + 1;
	}
	
	printf("%d\n", r);
	return 0;
}
算法
算法 前缀和 离散化

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！