HDU 6154 – CaoHaha's staff | 2017 中国大学生程序设计竞赛 – 网络选拔赛

/*
HDU 6154 - CaoHaha's staff [ 构造,贪心 ]  |  2017 中国大学生程序设计竞赛 - 网络选拔赛
题意：
整点图，每条线只能连每个方格的边或者对角线
问面积大于n的图形最少要几条线
分析：
可以发现面积相同的情况下，每条线都连对角的菱形是最优的
再考虑如何将 面积为x^2的菱形，每次扩展一条边, 按最优扩展为面积为(x+1)^2的菱形
然后就可以先二分，再判断了
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL binaryFind(LL l, LL r, LL x)
{
    LL mid;
    while (l <= r)
    {
        mid = (l+r)>>1;
        if (2*mid*mid > x) r = mid-1;
        else l = mid+1;
    }
    return r;
}
int t, n;
LL solve(LL k, LL n)
{
    if (k == 0) return 4;
    if (2*k*k >= n) return 4*k;
    if (2*k*k+k-0.5 >= n) return 4*k + 1;
    if (2*k*k+2*k >= n) return 4*k + 2;
    if (2*k*k+2*k+k+0.5 >= n) return 4*k+3;
    return 4*k+4;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        LL k = binaryFind(1, 1e8, n);
        printf("%lld\n", solve(k, n));
    }
}