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
}