Solution-P2239

CaiZi · 2024-12-29 22:41:44 · 题解

接下来的距离都是指曼哈顿距离，即 (a,b) 和 (c,d) 的距离为 |a-c|+|b-d|。

我们发现，对于每一圈的数字，左上角均为该圈的最小数字。因为每次螺旋完一圈后会回到该圈左上角下方，然后向右进入更小的一圈。记 (i,j) 外面共有 x 圈，那么显然 x=\min\{i-1,j-1,n-i,m-j\}。

然后我们发现第 i 圈有 4\times[n-2(i-1)]-4 个数字，化简一下，为 4n-8i+4。记 y 为前 x+1 圈的左上角的数字，那么：

\begin{aligned}y&=\sum_{i=1}^x(4n-8i+4)+1\\&=\sum_{i=1}^x4n-\sum_{i=1}^x8i+\sum_{i=1}^x4+1\\&=4xn-8\times\frac{x(x+1)}{2}+4x+1\\&=4xn-4x^2+1\end{aligned}

于是我们分类讨论一下 (i,j) 的位置，记 s 为答案：

如果 (i,j) 在该圈的上边一行或右边一行，即 i=x+1 或 j=n-x。此时答案为 y 加 (i,j) 到 (x+1,x+1) 的距离，即： \begin{aligned}s&=y+[i-(x+1)]+[j-(x+1)]\\&=y-2x+i+j-2\end{aligned}
其他情况时。此时答案为 y 加 (x+1,x+1) 到 (n-x,n-x) 加 (n-x,n-x) 到 (i,j) 的距离，即： \begin{aligned}s&=y+[(n-x)-(x+1)]+[(n-x)-(x+1)]+[(n-x)-i]+[(n-x-j)]\\&=y+2(n-2x-1)+2n-2x-i-j\\&=y-6x+4n-i-j-2\end{aligned}

时间复杂度 O(1)。

你会发现 y 基本没啥用，因此直接用 4xn-4x^2+1 代入两种情况的 y 即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,i,j,x;
signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>n>>i>>j;
    x=min({i-1,j-1,n-i,n-j});
    if(i==x+1||j==n-x){
        cout<<4*x*n-4*x*x-2*x+i+j-1;
    }
    else{
        cout<<4*x*n-4*x*x-6*x+4*n-i-j-1;
    }
    return 0;
}