Tom and paper

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/61

Description

Tom面前有一张纸，它的长和宽都是整数。Tom知道这张纸的面积n，他想知道这张纸的周长最小是多少。A的某一段完全重合，或者能够经过上下左右平移与折线A的某一段完全重合，则表示秋实大哥吹出了妹子的一部分旋律。

Input

有多组数据。第一行一个正整数T，表示数据组数。接下来T行，每行一个正整数n，表示纸的面积。
T≤10,n≤109

Output

对于每组数据输出一行一个整数，表示答案。

Sample Input

3
2
7
12

Sample Output

HINT

题意

题解：

枚举这张纸可能的长宽。因为面积为n的矩形必定存在一条边的边长不超过n√，所以只需枚举较短的边长，判断较长的边长是否是整数就可以了。
因为面积确定的矩形，长宽差越小，周长越小，所以可以从n√开始递减地枚举较短的边长，第一个合法的矩形就是答案。
时间复杂度：O（n√）

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

int main()

{

    int n;

    int t=read();

    while(t--)

    {

        n=read();

        int ans=;

        for(int i=sqrt(n+);i>=;i--)

        {

            if(i*(n/i)==n)

            {

                ans=(*i+*(n/i));

                break;

            }

        }

        cout<<ans<<endl;

    }

    return ;

}

秒客网

hdu 5224 Tom and paper 水题