第十三届 ACMCCPC 吉林省赛 E. Stick War

ACM/CCPC 历届真题 题解目录

Problem E. Stick War

Time Limit: 1000ms Memory Limit: 512MB 　 Description The Stick Kingdom will start a war to the Hammer Kingdom! The power of the stick army is the number of 1 ∗ 1 grids made up of sticks. The king of Stick Kingdom would give you the grids he needed, and you should tell him the minimum number of sticks he needed. Note: it’s very difficult for sticks to stand up, so the grids must be made on a 2-D plane. 　 Input First line contains an integer T (1 ≤ T ≤ 10v) represents the number of test cases. For each test case: The first line contains an integer n (1 ≤ n ≤ $10^6$) represents the number of grids the king needed. 　 Output For each test case, output a line contains an integer represents the minimum number of sticks the king needed. 　 Sample Input 4 1 2 3 4 　 Output 4 7 10 12 　 Hint

题目大意： 　　如上图方式用木棍拼方块，给你方块的数量，求最少需要用多少根木棍？ 　 分析： 　　根据题意，我们很容易发现，只有将小方块向大方块的形状上去拼，需要的木棍数量才是最少的。 　　那么我们就需要知道，$n$个小方块能拼成多大的大方块？答案是边长为$[\sqrt{n}]$的大方块("[]“代表向下取整)。 　 思路： 　　我们令$t=[\sqrt{n}]$，而： 　　1. 边长为$t$的大方块，需要$t\times (t+1)\times 2$根木棍拼成(自己证明)。 　　2. 边长为$t$的大方块需要$t\times t$个小方块。 　　注：这里$t=[\sqrt{n}]$的”[]"代表向下取整，也就是说，$[\sqrt{n}]\times [\sqrt{n}]$不一定等于$n$。如：$[\sqrt{5}]=2，2\times 2=4，即[\sqrt{5}]\times [\sqrt{5}]=4$。 　　我们令$v=n-t\times t$，即$n$个小方块拼成边长为$t$的大方块后，还多出$v$个小方块。 　　那么多出来的小方块怎么算？我们不难看出，边长为$t$的方块向边长为$t+1$的方块方向上去拼，只需要填充两条临边即可。如图： 　　根据上图，我们不难看出，多出一($v$)个小方块，就要多两($v\times 2$)根木棍，且每条边的起点处需要三根木棍。那么规律就出来了： 　　一共两条边，边长为$t$，每条边的第一个小方块需要三根木棍，即第$1$个小方块和第$t+1$个小方块各需要在$v\times 2$的基础上加一根木棍。所以多余的小方块需要木棍数量公式为：$$v\times 2+(v̸=0)+(v>t)$$　　其中$(v̸=0)$代表存在第一个小方块；$(v>t)$代表存在第$t+1$个小方块。所以，代码如下：

#include <iostream> #include <cmath> using namespace std; int t, n; int main() { scanf("%d", &t); while(t--) { scanf("%d", &n); int t = sqrt(n); //大方块边长t int v = n - t*t; //多v个小方块 int ans = t * (t+1) * 2; //大方块需要的木棍数量 ans += v * 2 + (v != 0) + (v > t); //加上v个小方块需要的木棍数量 printf("%d\n", ans); } return 0; }