Crazy tea party
| Time Limit: 1000MS | Memory Limit: 10000K | |
| |
|
Description
n participants of << crazy tea party >> sit around the table. Each minute one pair of neighbors can change their places. Find the minimum time (in minutes) required for all participants to sit in reverse order (so that left neighbors would become right, and
right - left).
right - left).
Input
The first line is the amount of tests. Each next line contains one integer n (1 <= n <= 32767) - the amount of crazy tea participants.
Output
For each number n of participants to crazy tea party print on the standard output, on a separate line, the minimum time required for all participants to sit in reverse order.
Sample Input
3
4
5
6
Sample Output
2
4
6
Source
题意很简单，n个人（1~n）围坐在一张桌子上，每分钟相邻两个人可以互换位置，求最少需要几分钟使得顺序变为逆序；
貌似普通思路没什么突破点，单纯找规律也找不出，但是我们可以发现题目只要求最后顺序为逆序，但没有指明位置不可以变；假如有5个人：1 2 3 4 5；变换之后是 3 2 1 5 4；明白了吧，结果只要是逆序排列就可以了，开始编号为1的人的位置可以任意，但一旦确定1的位置两边的位置就已经确定；假如最后1在编号为k的位置上，那么最后k就在开始编号为1的位置上，顺序就变成了：k~1、n~k+1;这样也是逆序的；
我们知道一个冒泡排序需要变换n*(n-1)/2;这里就可以分为两部分，1~k变换，需要变换k*(k-1)/2,剩下的n-k个数需要变换(n-k)*(n-k-1)/2;总共就是k*(k-1)/2+(n-k)*(n-k-1)/2；分解变成：k^2-nk+(n*n-n)/2;n为人数已知，求这个二元方程的最小值用（4ac-b^2）/4a;得答案为n/2*(n/2-1);但对于n的奇偶未知，思路已经提供到这了，奇偶问题应该不难解决；看代码：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(n%2==0)
printf("%d\n",n/2*(n/2-1));
else
printf("%d\n",n/2*((n+1)/2-1));
}
return 0;
}