hdu6154 CaoHaha's staff

题目：

在一个网格纸上，小网格是 1 * 1的。每次可以画一笔，这一笔可以是边长1，也可以是对角线$\sqrt2$。每次询一个面积 s,问最少画几笔，可以画出一个面积不小于 s 的图形。

分析：

同样画一笔，$\sqrt2$显然比1长。画一个1*1的小正方形需要4笔，而画一个$\sqrt2 *\sqrt2$的面积为2的小正方形也需要4笔。所以，肯定是画边长$\sqrt2$的正方形。以下出现的“正方形”均为边长为根号2的。

一个小正方形和一个大正方形之间差了4笔，一个恰能用小正方形满足的面积，肯定用小正方形。若不能满足，不要立刻换大正方形，在两个规格的正方形之间还有4笔没画，这4笔同样可以扩大面积。如何扩大这四笔，见下图。

顺序为：黑 -> 红 -> 蓝 -> 绿 -> 棕

总之，给任何一个面积，总能用这几种图形中的一个来满足。所以，对任意面积，分别计算用这几种图形来满足各需要几笔，取最小的就是答案。

代码：

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ms(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const double EPS=1e-8;
const int INF=0x3f3f3f3f;int main(){int T;ll ans,n;scanf("%d",&T);while(T--){scanf("%lld",&n);ll k1,k2,k3,k4;k1 = sqrt(n/2);while(2*k1*k1 < n){k1++;}k2 = (-1 + sqrt(5 + 8*n))/4;while(2*k2*k2+k2-0.5 < n+0.0){k2++;}k3 = (-1 + sqrt(1 + 2* n))/2;while(2*k3*k3 + 2*k3 < n){k3++;}k4 = (-3+sqrt(9-4+8*n))/4;while(2*k4*k4 + 3*k4 + 0.5 < n + 0.0){k4++;}ans = min(min(4*k1,4*k2+1),min(4*k3+2,4*k4+3));printf("%lld\n",ans);}   return 0;
}