自己动手画一下正方形,感觉就出来了
大正方形,假设是x阶,可以容纳x^2个小正方形
由题可知同一列或者同一行的边,如果大于1个,则只需要用一次尺子
因此在画小正方形时,每次依次填充到右侧,右侧填满以后填充到下方即可,这样可以使用最少的次数来绘制
注:(正方形上方和左侧,每次升阶的时候只需要借助两次尺子就可以从x阶变成x+1阶)
因此我们只需要对n进行开方取整,看tmp^2和n的大小关系
使用尺子的基础次数是tmp^2次(低阶正方形需要的次数)
(n - tmp * tmp) > tmp
: 添加2次
(n - tmp * tmp) <= tmp
: 添加1次
比如(懒得插图了,用 1 来代替小正方形):
画k阶正方形,基础次数是(k-1)^2,对应k-1阶的上方边和左侧边
画五个 :在四个的基础上填充到右侧,此时需要借助一次尺子来画坐标(1,3)的小正方形的上方边
1 1 1
1 1
画六个 : 继续填充右侧
1 1 1
1 1 1
画七个 : 右侧满了,填充到下方,此时需要借助一次尺子来画坐标(3,1)的小正方形的左侧边
1 1 1
1 1 1
1
代码如下
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T -- ){
int n , res = 0;
scanf("%d", &n);
int tmp = int(sqrt(n));
res = tmp * 2;
if(tmp * tmp < n){
if((n - tmp * tmp) > tmp) res += 2;
else res += 1;
}
printf("%d\n",res);
}
return 0;
}