首页 > ACM题库 > HDU-杭电 > hdu 2938 A poor officer待解决[解题报告]C++
2014
02-24

hdu 2938 A poor officer待解决[解题报告]C++

A poor officer

问题描述 :

There are n soldiers numbered from 1 to n in a troop. They stand in a line according to their numbers, which means the soldier numbered i stands at the ith position. But the officer of this troop is unsatisfied with the arrangement, he decides to rearrange it. After a careful consideration, the officer develops such rearrangement as follows: He thinks up a permutation of 1 to n, and then commands the aith soldier to stand in the ith position in the new arrangement. However, the new sequence still cannot meet the officer’s need. So they have to apply the arrangement repeatedly according to the method the officer thinks up.

For example, there are 5 soldiers in the troop; the permutation in the officer’s mind is 2 1 4 5 3. After the first rearrangement, the troop sequence is 2 1 4 5 3. After the second rearrangement, the sequence becomes 1 2 5 3 4.

Unluckily, after a long time of rearrangements, the officer and the soldiers are very tired but the strict officer is still unsatisfied. The poor officer asks the soldiers, “Who can tell me the least times of rearrangements needed to reach the arrangement I like.” As the smartest soldier you decide to answer the officer’s question.
Here is an example: if there are 5 soldiers in the troop, the permutation in the officer’s mind is 2 1 4 5 3. He wants the troop to be 2 1 3 4 5. The rearrangements are as follows:

输入:

The input contains several cases. Each case is described as follows:

1st line: n, the number of soldiers (0 < n ≤ 10,000).

2nd line: a1 a2 … an, the permutation that the troop applies each time.

3rd line: b1 b2 … bn, the target arrangement the officer is satisfied with.

The last case is followed by a line containing one zero.

输出:

The input contains several cases. Each case is described as follows:

1st line: n, the number of soldiers (0 < n ≤ 10,000).

2nd line: a1 a2 … an, the permutation that the troop applies each time.

3rd line: b1 b2 … bn, the target arrangement the officer is satisfied with.

The last case is followed by a line containing one zero.

样例输入:

5
2 1 4 5 3
2 1 3 4 5
0

样例输出:

3


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 您没有考虑 树的根节点是负数的情况, 若树的根节点是个很大的负数,那么就要考虑过不过另外一边子树了