题目描述
你有一堆棍子。每个木棒的长度是一个正整数。
你想要一组棍子所有的棍子都有相同的长度。您可以通过执行零个或多个步骤来更改当前集合。每个步骤必须如下所示:
你选择一根棍子。所选棒的长度必须至少为2。设L为所选木棍的长度。
如果L是偶数，把棍子切成两根长度为L/2的棍子。否则，把它切成长度为(L-1)/2和(L+1)/2的棒。把两根新棍子中的一根留下，把另一根扔掉。
可以证明，任何一种集合都可以变成一种长度相同的集合。给定当前棍子集合的长度，计算并返回达到目标所需的最小步骤数。
输入
多组数据，第一行一个整数T，表示数据组数,T<=6
每组数据：
第一行一个整数N，表示棍子数目。(2<=N<=50)
第二行N个整数，a[i]表示第i个棍子的长度。（1<=a[i]<=10^9）
输出
输出达到目标所需的最小步骤数
样例输入
4
2
11 4
4
1000 1000 1000 1000
7
1 2 3 4 5 6 7
6
13 13 7 11 13 11
样例输出
3
0
10
11
Solution
这道题需要注意的是当棍子长度是奇数的时候情况是不唯一的;
这样如果存储所有可能的状态是 (2^30) 级别的, 显然不能承受.
但是我们发现一个 性质 : 对于一个长度是奇数的棍子, 执行 k 次操作的可能长度只有 2 种, 这是因为当一个奇数被分成 奇数+偶数 时, 偶数接下来的所有情况都会被包含在奇数里. 所以偶数往下延伸的情况是没有必要的,每一层只有 1 个节点会往后延伸, 每一层最多只有 2 个节点.
这有点像线段树的性质.
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n, step[55][31][2], maxstep[55];
inline int solve(int len){
int ans = 0;
for (int i = 1; i <= n; ++i){
bool check = false;
for (int j = 0; j <= 30; ++j)
if (step[i][j][0] == len || step[i][j][1] == len){
ans += j;
check = true;
break;
}
if (!check) return 100000000;
}
return ans;
}
int main(){
int T; scanf("%d", &T);
while (T--){
scanf("%d", &n); memset(step, 0, sizeof(step));
for (int i = 1; i <= n; ++i){
scanf("%d", &step[i][0][0]);
maxstep[i] = 0; int x = step[i][0][0];
while (x > 1){
++maxstep[i];
if (x % 2 == 0) step[i][maxstep[i]][0] = x / 2, x = x / 2;
else{
step[i][maxstep[i]][0] = (x-1) / 2;
step[i][maxstep[i]][1] = (x+1) / 2;
if (x % 4 == 1) x = (x+1) / 2;
else x = (x-1) / 2;
}
}
}
/*for (int i = 1; i <= n; ++i)
for (int j = 0; j <= maxstep[i]; ++j)
printf("(%d,%d)%c", step[i][j][0], step[i][j][1], (j < maxstep[i]) ? ' ' : '
');*/
int Ans = 100000000;
for (int i = 0; i <= maxstep[1]; ++i){
for (int j = 0; j <= 1; ++j)
if (step[1][i][j]){
Ans = min(Ans, solve(step[1][i][j]));
}
}
printf("%d
", Ans);
}
return 0;
}