小红的马时间限制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 ) (xdx, ydy)(xdx,ydy)中其中( 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) (x1dx, y1dy)(x2,y2)(x1dx,y1dy)。若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。读入与标记用maparrayll,2, bool v标记所有兵的位置。统计候选遍历v中每个兵对其 8 个偏移位置若合法则c[{x2,y2}]。寻找最优使用max_element找到c中值最大的键输出该键坐标。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constarrayarrayll,2,8dd{{{-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;cinn;maparrayll,2,boolv;for(ll i0;in;i){ll x,y;cinxy;v[{x,y}]true;}maparrayll,2,llc;for(constauto[p,_]:v){constauto[x1,y1]p;for(constauto[dx,dy]:dd){ll x2x1dx,y2y1dy;if(x20||y20)continue;c[{x2,y2}];}}constauto[x,y]max_element(c.begin(),c.end(),[](constautoa,constautob){returna.secondb.second;})-first;coutx y\n;return0;}