思路

step1:暴力

观察到坐标的范围不大，$x$、$y$ 都是 $1000$ 以内的。所以直接将每个敌人放入坐标系中再枚举坐标系的每个 $a*b$ 的矩形求出矩形内的敌人数量即可。

复杂度$O(x^4)$

step2:前缀和优化

对于求每个$a * b$的矩阵的敌人数量时，我们可以使用二维前缀和优化，计算敌人复杂度从$O(a*b)$ 降至$O(1)$ 。

复杂度:$O(x^2)$

二维前缀和知识点学习:https://oi-wiki.org/basic/prefix-sum/

类似题目推荐

leetcode

1. 363.最大子矩阵和
2. 560.和为 K 的子数组
3. 304.二维区域和检索 - 矩阵不可变
4. 325.和为 K 的最长子数组长度

Codefun2000

P1195.华为实习-2023.04.19-第一题-塔子哥监考

代码

python

# 读入数据
n, a, b = map(int, input().split())

# 初始化二维矩阵
mp = [[0]*1011 for i in range(1011)]
# 将敌人放入矩阵
for i in range(n):
    x, y = map(int, input().split())
    mp[x][y] += 1       
# 对矩阵求前缀和
for i in range(1, 1011):
    for j in range(1, 1011):
        # 转移方程解释见Oi-Wiki
        mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1]
# 枚举技能矩阵(的右下角)
ans = 0
for i in range(a+1, 1011):  #枚举右上端点
    for j in range(b+1, 1011):      #此时枚举的矩形为 (i-a, j-b) 到 (i,j)之间的矩形
        t = mp[i][j] - mp[i-a-1][j] - mp[i][j-b-1] + mp[i-a-1][j-b-1]
        ans = max(ans, t)
print(ans)

C++

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

int n, a, b;
int mp[1011][1011];

int main() {
    // 读入数据
    cin >> n >> a >> b;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        mp[x][y]++;
    }
    // 对矩阵求前缀和
    for(int i = 1; i <= 1010; i++) {
        for(int j = 1; j <= 1010; j++) {
            mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];
        }
    }
    // 枚举技能矩阵的右下角，并求矩形伤害总和的最大值
    int ans = 0;
    for(int i = a+1; i <= 1010; i++) {
        for(int j = b+1; j <= 1010; j++) {
            int t = mp[i][j] - mp[i-a-1][j] - mp[i][j-b-1] + mp[i-a-1][j-b-1];
            ans = max(ans, t);
        }
    }
    cout << ans << endl;
    return 0;
}

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int[][] mp = new int[1011][1011];
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            mp[x][y]++;
        }

        // 求二维前缀和
        for(int i = 1; i <= 1010; i++) {
            for(int j = 1; j <= 1010; j++) {
                mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];
            }
        }

        // 枚举技能矩阵的右下角，并求矩形伤害总和的最大值
        int ans = 0;
        for(int i = a+1; i <= 1010; i++) {
            for(int j = b+1; j <= 1010; j++) {
                int t = mp[i][j] - mp[i-a-1][j] - mp[i][j-b-1] + mp[i-a-1][j-b-1];
                ans = Math.max(ans, t);
            }
        }

        System.out.println(ans);
    }
}

js

// 监听标准输入流的 data 事件，读取输入的数据并保存到变量 input 中
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});

// 监听标准输入流的 end 事件，在所有数据读入完成后执行核心代码
process.stdin.on('end', () => {
    // 按行分割输入数据，并解析出采用空格分割的三个整数值 n、a 和 b
    const lines = input.trim().split('\n');
    let n, a, b;
    n = parseInt(lines[0].split(' ')[0]);
    a = parseInt(lines[0].split(' ')[1]);
    b = parseInt(lines[0].split(' ')[2]);

    // 创建一个二维数组 mp 用于存储每个点是否被击中
    let mp = [];
    for(let i = 0; i < 1011; i++) {
        mp[i] = new Array(1011).fill(0);
    }

    // 循环读入 n 行数据，并将每个坐标对应的位置标记为已击中
    for(let i = 1; i <= n; i++) {
        let x = parseInt(lines[i].split(' ')[0]);
        let y = parseInt(lines[i].split(' ')[1]);
        mp[x][y]++;
    }

    // 对矩阵求前缀和，通过累加计算矩形内所有击中点的个数
    for(let i = 1; i <= 1010; i++) {
        for(let j = 1; j <= 1010; j++) {
            mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];
        }
    }

    // 枚举技能矩阵的右下角，并求矩形伤害总和的最大值
    let ans = 0;
    for(let i = a+1; i <= 1010; i++) {
        for(let j = b+1; j <= 1010; j++) {
            let t = mp[i][j] - mp[i-a-1][j] - mp[i][j-b-1] + mp[i-a-1][j-b-1];
            ans = Math.max(ans, t);
        }
    }

    // 输出结果
    console.log(ans);
});

go

package main

import (
	"fmt"
)

func main() {

	var n, a, b, x, y int
	fmt.Scan(&n, &a, &b)
	N := 1005
	x_y := make([][]int, N)
	for i := 0; i < N; i++ {
		x_y[i] = make([]int, N)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&x, &y)
		x_y[x][y] = x_y[x][y] + 1
	}

	//计算前缀和.
	for i := 1; i < N; i++ {
		for j := 1; j < N; j++ {
			x_y[i][j] = x_y[i][j-1] + x_y[i-1][j] - x_y[i-1][j-1] + x_y[i][j]
		}
	}
	//计算小矩阵.
	max_v := 0
	for i := a + 1; i < N; i++ {
		for j := b + 1; j < N; j++ {
			t := x_y[i][j] - x_y[i-a-1][j] - x_y[i][j-b-1] + x_y[i-a-1][j-b-1]
			max_v = max(max_v, t)
		}
	}
	fmt.Println(max_v)
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

题目内容

在一个荒凉的大漠中，小美被派遣去完成一个秘密任务：消灭在这片区域活动的敌军。这片区域广阔辽阔，有着无尽的沙丘和荒凉的山峰，许多敌人藏匿在这些地方，等待着小美的到来。

为了提高效率，小美使用了一款高级游戏模拟器，在虚拟的游戏环境中，他可以通过控制游戏角色来模拟现实世界中的作战行动。这款游戏的目标是尽可能地抓获敌人。

在游戏中，敌人的位置将被一个二维坐标$(x,y)$所描述。小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。捕获的敌人之间的横坐标的最大差值不能大于$A$，纵坐标的最大差值不能大于$B$。

现在，小美来到了游戏的一个新关卡，他需要在规定时间内消灭尽可能多的敌人。他打开了游戏地图，看到了所有敌人的坐标。他立刻开始思考，如何才能最大限度地利用自己的技能，一次性捕获尽可能多的敌人。

输入描述

第一行三个整数$N,A,B$，表示共有$N$个敌人，小美的全屏技能的参数$A$和参数$B$。

接下来$N$行，每行两个数字$x,y$，描述一个敌人所在的坐标

$1 \leq N \leq 500$，$1 \leq A,B \leq 1000，1 \leq x,y \leq 1000$

输出描述

一行,一个整数表示小美使用技能单次所可以捕获的最多数量。

样例$1$

输入

3 1 1
1 1
1 2
1 3

输出

2

说明： 最多可以同时捕获两名敌人，可以是$(1，1)$和$(1，2)$处的敌人，也可以是$(1，2)$和$(1，3)$处的敌人，但不可以同时捕获三名敌人，因为三名敌人时，纵坐标的最大差值是$2$，超过了参数$B$的值$1$。

样例$2$

输入

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

输出

3

说明

最多同时捕获三名敌人。其中一种方案如下: 捕获$(1， 1)$， $(1，3)$，$(2，2)$处的三个敌人。