HDU 1214 圆桌会议 圆环逆序

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;
}
上一篇:docker安装JDK1.8版本


下一篇:gson Expected BEGIN_OBJECT but was BEGIN_ARRAY at line 1 column 2 path