小红的马
时间限制：3秒 空间限制：1024M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红在玩国际象棋。在一个无限大的棋盘上，有n nn个兵。小红想找一个没有兵占据且行号与列号均为正整数的格子放置一个马，并使得马能攻击到的兵的数量最多。请你帮他找到任意一个满足该条件的位置。
马可攻击的八个位置如下图所示（注意，您无需考虑中国象棋中的蹩马腿规则）。
输入描述：
第一行输入一个整数n ( 1 ≦ n ≦ 2 × 10 5 ) n(1≦n≦2×10^5)n(1≦n≦2×105)。
之后的n nn行，第i ii行输入两个整数x i , y i ( 1 ≦ x i , y i ≦ 2 × 10 5 ) x_i,y_i(1≦x_i,y_i≦2×10^5)xi,yi(1≦xi,yi≦2×105)，代表第i ii个兵的位置为第x i x_ixi 行第y i y_iyi列。保证所有兵的位置两两不同。
输出描述：
输出两个正整数，分别代表符合条件的行号与列号。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测功能可能因此返回答案错误结果，请自行检查答案正确性。
示例1
输入：
3 1 2 2 3 3 2输出：
1 1说明：
在这个样例中，棋盘的布局如下（左下角为(1,1)）：示例2
输入：
4 1 4 4 1 2 2 3 3输出：
1 2说明：
在这个样例中，棋盘的布局如下（左下角为(1,1)）：解题思路
本题是离线计数 + 枚举的经典模型。由于马能攻击到的格子为固定的 8 个日字形偏移，反过来，对于每个兵，所有能攻击到该兵的位置只有这 8 个偏移坐标。因此，只需遍历所有兵，将每个可能的马位置累计攻击次数，最后选取攻击次数最多的位置作为答案。
1. 问题等价转化
- 马攻击规则：马可以攻击到相对其位置( d x , d y ) (dx,dy)(dx,dy)满足∣ d x ∣ , ∣ d y ∣ |dx|,|dy|∣dx∣,∣dy∣分别为1 , 2 1,21,2或2 , 1 2,12,1的 8 个位置。
- 反向思考：若某个位置放置马能攻击到兵( x , y ) (x,y)(x,y)，则( x , y ) (x,y)(x,y)相对于马的位置必须是上述 8 个偏移之一。也就是说，马的位置必然在( x + d x , y + d y ) (x+dx, y+dy)(x+dx,y+dy)中，其中( d x , d y ) (dx,dy)(dx,dy)来自 8 个偏移向量。
- 目标：对于所有兵，统计每个可能放置马的位置能攻击到的兵数量，找到最大值对应的位置，且要求该位置没有兵占据（代码中未显式排除，但实际数据可能满足或允许稍后判断；核心是统计最大攻击数）。
2. 算法实现
- 存储兵位置：用
map存储所有兵坐标，便于快速查找和遍历。 - 统计候选位置攻击数：
- 遍历每个兵( x 1 , y 1 ) (x1,y1)(x1,y1)。
- 对 8 个偏移( d x , d y ) (dx,dy)(dx,dy)，计算候选马位置( x 2 , y 2 ) = ( x 1 + d x , y 1 + d y ) (x2,y2) = (x1+dx, y1+dy)(x2,y2)=(x1+dx,y1+dy)。
- 若x 2 ≤ 0 x2 \le 0x2≤0或y 2 ≤ 0 y2 \le 0y2≤0，跳过（马必须在正整数行列）。
- 在计数器
map中令c[{x2,y2}]++，表示该位置能攻击到的兵数加一。
- 选取最优位置：遍历计数器
c，找到值最大的位置，输出其坐标。- 使用
max_element按值比较即可。
- 使用
3. 复杂度分析
- 时间复杂度：每个兵贡献 8 个候选位置，总操作O ( 8 n ) O(8n)O(8n)；
map的操作时间复杂度为O ( log n ) O(\log n)O(logn)，总复杂度O ( n log n ) O(n \log n)O(nlogn)。n ≤ 2 × 10 5 n \le 2\times 10^5n≤2×105，完全可以接受。 - 空间复杂度：需要存储所有兵位置和所有候选位置，最坏O ( 8 n ) O(8n)O(8n)，约1.6 × 10 6 1.6\times 10^61.6×106个键值对，空间充足。
总结
通过反向枚举每个兵可能被攻击到的马位置，统计各候选位置的攻击次数，再取最大者，即可得到最优放置位置。整个过程无需考虑棋盘大小，只需保证坐标为正整数。
代码简要说明
- 偏移数组：预定义 8 个马步偏移
dd。 - 读入与标记：用
map<array<ll,2>, bool> v标记所有兵的位置。 - 统计候选：遍历
v中每个兵，对其 8 个偏移位置若合法则c[{x2,y2}]++。 - 寻找最优：使用
max_element找到c中值最大的键，输出该键坐标。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constarray<array<ll,2>,8>dd={{{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}};intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;map<array<ll,2>,bool>v;for(ll i=0;i<n;i++){ll x,y;cin>>x>>y;v[{x,y}]=true;}map<array<ll,2>,ll>c;for(constauto&[p,_]:v){constauto&[x1,y1]=p;for(constauto&[dx,dy]:dd){ll x2=x1+dx,y2=y1+dy;if(x2<=0||y2<=0)continue;c[{x2,y2}]++;}}constauto&[x,y]=max_element(c.begin(),c.end(),[](constauto&a,constauto&b){returna.second<b.second;})->first;cout<<x<<" "<<y<<"\n";return0;}
