n人组成一个环，求做相邻交换的操作最少多少次可以使每个人左右的邻居互换，即原先左边的到右边去，原右边的去左边。

先只考虑排成一列的情况。由于只能在邻居之间交换。相当于用冒泡排序排列n..1，需（n-1）n/2（∵T(n) = n-1 + T(n)）

然后考虑将环转换为非环。即(k k-1 .. 1) (n .. k+1)例如：1 2 3 4 5 6的目标可以是 6 5 4 3 2 1,也可以是 (4 3 2 1 )(6 5)。相对于对两部分分别排序，
inv（n） = min{ (k×(k-1)/2) + ((n-k)×(n-k-1)/2) | 1≤k≤n }。

当n为奇数（n=2k+1）时，inv（n） = k×k；
当n为偶数（n=2k）时，inv（n） = k×k - k；

可统一为inv（n） = floor（n/2）×floor((n-1)/2)（floor为下取整函数）。

# include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;
        cout << (m/2)*((m-1)/2) << endl;
    }
    return 0;
}


[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]