1. 捕获敌人
题目描述
小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。
敌人的位置将被一个二维坐标(x,y) 所描述。
小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。捕获的敌人之间的横坐标的最大差值不能大于 A，纵坐标的最大差值不能大于 B 。
现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。
输入描述
第一行三个整数 N*,A,B，表示共有 N* 个敌人，小美的全屏技能的参数 A 和参数 B。
接下来 N 行，每行两个数字 x,y，描述一个敌人所在的坐标。
1⩽N⩽500,1⩽A,B⩽1000,1⩽x,y⩽1000
输出描述
一行，一个整数表示小美使用技能单次所可以捕获的最多数量。
样例1
输入
输出
说明：最多可以同时捕获两名敌人，可以是 (1,1)(1,1) 和 (1,2)(1,2) 处的敌人，也可以是 (1,2)(1,2) 和 (1,3)(1,3) 处的敌人，但不可以同时捕获三名敌人，因为三名敌人时，纵坐标的最大差值是 22，超过了参数 B* 的值 11。
题解
二维前缀和：就是在一个大矩形中有若干个点，给我们一个小矩阵，看它最多能框住多少个点。
所以我们先读入敌人坐标，将有敌人的坐标初始化为 1。
然后用二维前缀和预处理，再枚举每一个范围内 (A,B) 的子矩阵，取一个 max即可。
时间复杂度 O(N2)
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
| import java.util.Scanner;
public class Main {
static final int N = 1000;
static int[][] g = new int[N + 10][N + 10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
a++; b++;
a = Math.min(a, N);
b = Math.min(b, N);
for (int i = 0; i < n; i++) {
int x = sc.nextInt(), y = sc.nextInt();
g[x][y]++;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
}
}
int res = 0;
for (int i = a; i <= N; i++) {
for (int j = b; j <= N; j++) {
res = Math.max(res, g[i][j] - g[i - a][j] - g[i][j - b] + g[i - a][j - b]);
}
}
System.out.println(res);
}
}
|
2. 截彩带
题目描述
小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。
因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过 K 种。
显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过 K 种。
输入描述
第一行两个整数 N*,K，以空格分开，分别表示彩带有 N* 厘米长，你截取的一段连续的彩带不能超过 K* 种颜色。接下来一行 N* 个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。
1≤N,K≤5000，彩带上的颜色数字介于 [1,2000][1,2000] 之间。
输出描述
一行，一个整数，表示选取的彩带的最大长度。
样例
输入
输出
说明：最长的一段彩带是 [1,2,3,2,1][1,2,3,2,1] 共 55 厘米。
题解
求连续子数组最大和，但此题还要求区间的种类数不能超过 K* 种，所以在双指针的基础上我们还需要用 哈希 来维护区间的种类数。
暴力解法
直接两重循环，用 set 维护区间种类数。
时间复杂度 O*(N2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
int res = 0;
for (int i = 0; i < n; i++) {
Set<Integer> set = new HashSet<>();
for (int j = i; j < n; j++) {
set.add(a[j]);
if (set.size() > k) break;
res = Math.max(res, j - i + 1);
}
}
System.out.println(res);
}
}
|
双指针 + map
时间复杂度 O*(N)
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
| import java.util.Scanner;
public class Main {
static final int N = 5010;
static int[] cnt = new int[N];
static int num;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
int res = 0;
for (int i = 0, j = 0; i < n; i++) {
a[i] = sc.nextInt();
add(a[i]);
while (num > k) {
sub(a[j]);
j++;
}
res = Math.max(res, i - j + 1);
}
System.out.println(res);
}
private static void add(int x) {
if (++cnt[x] == 1) num++;
}
private static void sub(int x) {
if (--cnt[x] == 0) num--;
}
}
|