http://acm.hdu.edu.cn/showproblem.php?pid=1214
题目大意:
一群人围着桌子座,如果在一分钟内一对相邻的人交换位置,问多少分钟后才能得到与原始状态相反的座位顺序。(相反顺序:即对于每个人,原先在他左面的人后来在他右面,原先在他右面的人在他左面)
思路:
如果是一条直线的话,那么就像冒泡排序一样,需要的次数为n*(n-1)/2
但是这里是环形的。
办法是分成一半,每一半的人逆序。
这样需要 a*(a-1)/2 + b*(b-1)/2次,其中b=n-a,a=n/2;
为什么是一半?
把b=n-a带入上式得:
(2*a^2-2*n*a+n^2-n)/2
可以得到,在抛物线的中点有最小值。。即a=-(-2*n/(2*2))=n/2
#include<cstdio>
int main()
{
int n;
while(~scanf("%d",&n))
{
int a=n/2;
int b=n-a;
printf("%d\n", a*(a-1)/2 + b*(b-1)/2);
}
return 0;
}