http://acm.pku.edu.cn/JudgeOnline/problem?id=1455
如果所有人是線性排列,那我們的工作就是類似冒泡程序做的工作,,1,2,3,4,5變為5,4,3,2,1 ,耗時n(n-1)/2
但是出現了環,也就是說1,2,3,4,5變為3,2,1,5,4也可滿足條件
我們可以把這個環等分成兩個部分 ,每個部分看成是線性的,再把它們花的時間加起來.
當n是偶數時, 每份人數n/2 ,即 (n/2-1)*(n/2)*2
當n是偶數時,兩份的人數分別是n/2和n-n/2,即(n/2-1)*(n/2)+ ((n-n/2)-1)*(n-n/2)/2
適當化簡,得到以下程序
Source
Problem Id:1455 User Id:lnmm
Memory:88K Time:0MS
Language:C++ Result:Accepted
1
#include"iostream.h"
2
3void main()
4
{
5
int T;
6 int n;
7 int temp;
8 int a,b;
9 cin>>T;
10 while(T--)
11
{
12 cin>>n;
13 if(n%2==0)
14 {
15 temp=(n/2-1)*n/2;
16
}
17 else
18 {
19 a=n/2;
20 b=n-n/2;
21 temp=((a-1)*a+(b-1)*b)/2;
22
23 }
24 cout<<temp<<endl;
25
26 }
27
}