这道题已经明显地告诉我们了:
对于100%的数据,1 ≤ n ≤ 30,000,1 ≤ i ≤ n,1 ≤ j ≤ n
所以模拟填数会TLE
所以说
找规律大法好 orz
我和很多人的思路一样,先确定要求的数在哪一层(变量名:m)。但之后我是把所在层左上角上的数(变量名:flag)算出来,再根据要求的数在当前层的新的位置,用flag推算出来。
看一个模拟表格
1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|
16 | 17 | 18 | 19 | 6 |
15 | 24 | 25 | 20 | 7 |
14 | 23 | 22 | 21 | 8 |
13 | 12 | 11 | 10 | 9 |
输入 5 4 2
如果人脑用我的方法模拟的话,应该是这样的:
- 第四行第二列的数在第二层
- 所在层左上角的数是17
- 要求的数的新位置是3 1
- 要求的数在17的正下方,且与17的距离为2
- 要求的数是23
大致是这么一个过程
接下来该上代码了
#include<bits/stdc++.h>
using namespace std;
int ans,x,y,flag;
int main()
{
//输入
int n,i,j;
cin>>n>>i>>j;
//计算层数 ,m就是要求数所在的层数。if的作用就懒得说了,自己看吧
if(i>n/2)
y=n-i+1;
else
y=i;
if(j>n/2)
x=n-j+1;
else
x=j;
int m=min(x,y);
//求所在层的左上角的数
flag=1;
for(int k=1;k<=m-1;k++)
{
flag+=4*(n-1);
n-=2;
}
//根据新位置求数
int x2=i-m+1,y2=j-m+1;//数在层上的新位置是x2行,y2列
//四个if判断该数在左上角的哪个位置
if(x2==1) //正右方 即表格中的2/3/4/5(假设以1为左上角,下同)
{
cout<<flag+y2-1;
return 0;
}
if(y2==1)//正下方 即表格中的16/15/14/13
{
cout<<flag+4*(n-1)-1-x2+2;
return 0;
}
if(y2>x2)//右下角的正上方 即表格中的6/7/8
{
cout<<flag+n-1+x2-1;
return 0;
}
if(x2>y2) //右下角的正左方 即表格中的12/11/10
{
cout<<flag+4*(n-1)-1-n+2-y2+1;
return 0;
}
if(x2==y2) //右下角 即表格中的9
{
cout<<flag+(n-1)+(n-2)+1;
return 0;
}
return 0;
}
语言表述能力有限,敬请原谅。 如有错误,可以私信我