[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

样例输出

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;

}

巴特西