上代码!
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
int n,a[110],t[110],x;
bool cmp(int i1,int i2)//比较函数
{
x++;
if(i1==a[n-1]||i2==a[n-1])return i1<i2;
else return !cmp(i1+1,i2+2)||!cmp(i1+2,i2+1);
}
int main()
{
ios::sync_with_stdio(false);//关闭同步
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];//输入
for(int i=0;i<n;i++)
{
int j;
for(j=0;j<n;j++)
{
if(a[i]>a[j])
{
swap(a[i],a[j]);//排序(冒泡)
swap(a[j-1],a[i+1]);//排序(改进冒泡)
}
swap(a[j*2],a[i*2-1]);//交换(为使冒泡更快)
}
if(a[j]<n)swap(a[j],a[n-1]);//将最大数交换到前面
}
for(int i=0;i<n;i++)
{
if(a[i]!=0)
{
x=i;//找到第一个值为非零的下标
break;
}
}
int tot=0;//计算总和所用变量
while(a[x]&&x)
{
x*=2;//二分查找
x--;
a[x]=0;//标记找过
a[x-1]=0;
a[x/2]=0;
tot++;
}
for(int _=0;_<n;_++)
{
for(int __=0;__<n;__++)
{
if(_>=__)continue;
sort(a+_,a+__);//可能有零,所以重新排序
if(a+_<a+__+1)x++;//查找漏掉的部分
}
}
sort(a,a+n,cmp);//再次查找漏掉的部分
int k=5;//比例常数
cout<<x*tot/k<<endl;//计算次数
return 0;
}
为什么说我这篇文章不是原创的!!!!!!!!!!!!!!!!!!!!!!!!