POJ 1455 Crazy tea party

Description

Input

Output

Sample Input

3
4
5
6

Sample Output

2
4
6

大家都清楚假定是一排的情况下：

1 2 3 4 5 6 7

如果位置交换后：

7 6 5 4 3 2 1

需要经过n*(n-1)/2次交换（冒泡法进行交换）

现在情况是环形，试问能不能将环拆分成两个线性，然后进行交换，再拼接在一起。

举例如下：

1 2 3 4 5 6 7（7后面又是1）

如果分成1 2 3 ，4 5 6 7两部分，分别进行逆序，然后连接，是不是满足条件呢？

交换后3  2 1, 7 6 5 4

连接后为：3  2 1 7 6 5 4，在环路中，其实位置更改后为7654321，是满足条件的。

那么题目得解：

现在问题是假定环形的长度是N，如果进行截图，才能使得交换次数是最少的呢？
假定N的环形，分成一个长度为k，另一个长度是N-k的线段。

那么需要交换的次数为：

k*(k-1)/2

(N-k)*(N-k-1)/2

相加后就是需要交换的总次数。

题目要求交换次数最少。

那么就是求 

k*(k-1)/2+

(N-k)*(N-k-1)/2的最小值。

很容易根据公式，二次函数在极值时取N/2的时候。

--------------------------AC---------------------------------

#include<stdio.h>


int main()
{
int n,m;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
printf("%d\n",m/2*(m/2-1)/2+(m+1)/2*((m+1)/2-1)/2);

}
return 0;
} 

POJ 1455 Crazy tea party,布布扣,bubuko.com

POJ 1455 Crazy tea party

原文：http://blog.csdn.net/zzucsliang/article/details/21127153