CCPC网赛 CaoHaha's staff（找规律+模拟扩展正方形）

末蓝、 2022-06-10 13:06 96阅读 0赞

"You shall not pass!"  
After shouted out that,the Force Staff appered in CaoHaha's hand.  
As we all know,the Force Staff is a staff with infinity power.If you can use it skillful,it may help you to do whatever you want.  
But now,his new owner,CaoHaha,is a sorcerers apprentice.He can only use that staff to send things to other place.  
Today,Dreamwyy come to CaoHaha.Requesting him send a toy to his new girl friend.It was so far that Dreamwyy can only resort to CaoHaha.  
The first step to send something is draw a Magic array on a Magic place.The magic place looks like a coordinate system,and each time you can draw a segments either on cell sides or on cell diagonals.In additional,you need 1 minutes to draw a segments.  
If you want to send something ,you need to draw a Magic array which is not smaller than the that.You can make it any deformation,so what really matters is the size of the object.  
CaoHaha want to help dreamwyy but his time is valuable(to learn to be just like you),so he want to draw least segments.However,because of his bad math,he needs your help.

Input

The first line contains one integer T(T<=300).The number of toys.  
Then T lines each contains one intetger S.The size of the toy(N<=1e9).

Output

Out put T integer in each line ,the least time CaoHaha can send the toy.

Sample Input

5
    1
    2
    3
    4
    5

Sample Output

4
    4
    6
    6
    7

题解：

比赛当时没想出来。。后来学长说了是找规律四次扩展以后就想了一会，推出了公式。。。这题还真有意思

题意：

输入一个面积，你只能用单位长1或者是单位格子的斜边根号2的边来围成这个图形，问最短为多少，注意围成的面积可以大于输入的值

思路：

我们可以每一条直边的贡献是1，而每一条斜边的贡献是根号2，所以越多斜边越好，而这些斜边如何摆放使得面积最大呢，就是用这些斜边组成一个正方形，那其他情况呢，根据找规律我们可以得出有四次扩展，每次扩展用的边数+1，但是得到新增的面积是最大化的，请看图

![Center][]

我们把里面的正方形进行扩展，共扩展4次得到一个新的正方形，我用红白相间标出了每次扩展的部分，然后根据平行关系推一下公式就好了，看他要求的面积在哪个区间里面，输出边数就是了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int main()
    {
        ll i,j,test,n;
        scanf("%lld",&test);
        while(test--)
        {
            scanf("%lld",&n);
            if(n==1)//特殊处理下1
            {
                printf("4\n");
                continue;
            }
            int d=sqrt(n*1.0)/sqrt(2.0);//最初的正方形斜边长度
            if(d*d*2>=n)//没进行扩展的情况
            {
                printf("%lld\n",4*d);
                continue;
            }
            if(d*d*2+(2*d-1)/2>=n)//扩展1次的情况，后面以此类推
            {
                printf("%lld\n",4*d+1);
                continue;
            }
            if(d*d*2+2*d>=n)
            {
                printf("%lld\n",4*d+2);
                continue;
            }
            if(d*d*2+3*d+0.5>=n)
            {
                printf("%lld\n",4*d+3);
                continue;
            }
            printf("%lld\n",(d+1)*4);
        }
        return 0;
    }

[Center]: /images/20220610/37506530922e4254b14bfe94b5195af9.png