[TopCoder]棍子

棍子"/>

[TopCoder]棍子

题目描述

你有一堆棍子。每个木棒的长度是一个正整数。
你想要一组棍子所有的棍子都有相同的长度。您可以通过执行零个或多个步骤来更改当前集合。每个步骤必须如下所示:
你选择一根棍子。所选棒的长度必须至少为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]) ? ' ' : '\n');*/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\n", Ans);}return 0;
}

转载于:.html