Description

一个名叫"crazy tea"的组织有N个党员,经常坐在一张圆形的桌子上。
每一分钟，一对相邻的两个党员可以交换位子。
要求
对于给定数目N，求要多少时间才能得到与原始状态相反的座位顺序(reverse)
即对于每个党员，原先在他左面的党员后来在他右面，原先在他右面的党员在他左面。

Input

首先一个总数S,表示有s个数据
之后每个数据一行含一个整数N(1<=N<=32767)

Output

对每个数据输出一行，表示需要的时间(以分钟为单位)

Sample Input

3

4

5

6

Sample Output

2

4

6

Solve:

就是将这个序列按照降序用冒泡排序重排,比如1 2 3 4 - > 4 3 2 1,然后因为这是一个圆是有环的,所以就应该是折半逆序,第一个在中间,也就是另pre = n / 2，tail = n - pre

然后冒泡排序交换次数为c * (c - 1) / 2,所以答案就是pre * (pre - 1 ) / 2 + tail * (tail - 1 ) / 2

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 int n; 4 int main() 5 { 6     int t; 7     scanf("%d" , &t); 8     while(t--) 9     {10         scanf("%d" , &n);11         int a = n >> 1;12         int b = n - a;13         int ans = a * (a - 1) / 2 + b * (b - 1) / 2;14         printf("%d\n" , ans);15     }16 17 }

View Code

BZOJ1133: 变态茶党(数学)