小美抓敌人

Problem Description

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。 敌人的位置将被一个二维坐标(x,y)所描述。
小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B
现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

input

第一行三个整数N,A,B，表示共有N个敌人，小美的全屏技能的参数A和参数B。 接下来N行，每行两个数字x,y，描述一个敌人所在的坐标。
1≤N≤500，1≤A,B≤1000，1≤x,y≤1000

ouput

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

Sample Input 1

3 1 1
1 1
1 2
1 3

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

题目类型、难度、来源

• 类型：滑动窗口、排序
• 难度：简单
• 来源：美团校招-2023.3.18.10点-第一题-小美抓敌人

总体思路：

• 此题可以看成是二维的滑动窗口，先要在x轴进行一次，再在y轴进行一次。但由于数据量最多只有500，因此就不必杀鸡用牛刀了。直接暴力。
• 思路：
  • 按x坐标大小从小到大排序。
  • 遍历，每次找到最大的满足“敌人之间的横坐标的最大差值不能大于A”这个设定的区间，将这个最大区间里的y坐标存入数组ys中。
  • 给ys从小到大排序，然后找到最大的满足“纵坐标的最大差值不能大于B”这个设定的区间，记录区间里的敌人数量。

AC代码

#include 
#include 
using namespace std;
class Enemy{public:int x;int y;
};
bool com(Enemy &e1, Enemy &e2){if (e1.x == e2.x){return (e1.y < e2.y);}else{return (e1.x < e2.x);}
}
int main(){int N, A, B;cin >> N >> A >> B;Enemy *es = new Enemy[N+5];for (int i = 0; i < N; i++){cin >> es[i].x >> es[i].y;}sort(es, es+N, com);int max_num = -1;for (int i = 0; i < N; i++){int ys[N] = {0}, yn = 0;for (int j = i; j < N; j++){if (es[j].x-es[i].x > A){break;}else{ys[yn++] = es[j].y;}}sort(ys, ys+yn);for (int k = 0; k < yn; k++){int count = 0;for (int t = k; t < yn; t++){if (ys[t] - ys[k] <= B){count++;}else{break;}}if (count > max_num){max_num = count;}}}cout << max_num;return 0;
}