1217: 换位置(c语言）（提供思路）

解题思路:

如果人数为偶数i个，可以化归为两个i/2的人只能单向换顺序，我们已知将a个人排成长队逆序需要（a-1）*a/2次，所以共需要（i/2-1）*(i/2)次；

如果人数为奇数i个，化归为i-1个人排完之后再将最后一个人移位，(（i-1)/2-1）*((i-1)/2)+(i-1)/2;

图例：

偶数个以6个为例：

                                         |

                      6                 |              1

             5                          |                     2   

                       4                |              3

                                         |

从中间分开，将两侧分别看做排成长队之后的结果，则 1 2 3变为3 2 1需要（3-1）*3/2次，共需要（3-1）*3次

奇数以七个为例：

                                         1

                                         |

                      7                 |              2

             6                          |                     3  

                       5                |              4

                                         |

对下面几个操作完之后结果为：

                                         1

                                         |

                      5                 |              4

             6                          |                     3  

                      7                 |              2

                                         |

再经过（7-1）/2次将1移到最下面即可

                                         |

                      5                 |              4

             6                          |                     3  

                      7                 |              2

                                         |

                                         1

注意事项:

参考代码:

注：a[i]表示i+1个人换位置的时间

#include<stdio.h>

int main(void)

{

int i;

int n;

int m;

int a[32767]={0};

a[0]=0;

a[1]=0;

a[2]=1;

for(i=3;i<32767;i++)

{

if(i%2)

{

a[i]=((i+1)/2-1)*((i+1)/2);

}

else

{

a[i]=i*i/4;

}

}

scanf("%d",&n);

{

for(i=0;i<n;i++)

{

scanf("%d",&m);

printf("%d\n",a[m-1]); 

}

} 

return 0;

}