换位置-双向逆序

解题思路:

如果n个人如果是线性排列，要使123456…n变成n…654321， 那么需要的时间总数就是(n-1)+…+5+4+3+2+1=n*(n-1)/2；即1右移n-1步， 2右移n-2步…

再回到原题，由于是一个围成一个圈，所以可以双向移动。 例如：1234 567 变成4321 765也完成了顺序完全相反。 因而将n分为两部分，n/2和n-n/2，两部分独自逆序，可以实现时间最短。

注意事项:

参考代码:

#include<iostream>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while(t --){
		int n;
		cin >> n;
		if(n % 2 == 0){
			cout << n/2 * (n/2 - 1);
		}
		else{
			cout << n / 2 *(n / 2 - 1) + n / 2;
		}
		cout << endl;
	}	
	return 0;
}