问题标题: 酷町堂：2580

既然题目描述是冒泡排序，冒泡序是交换相邻的两个数的值，每次外层循环都会把当前数列中的相邻的两个位置错乱的值交换位置，根据题中算法，每次外层循环至少会将一个数向左交换最多一次，所以解题思路就是，用结构体记录原本在数组中位置，排序后找出向左交换次数最多的数，输出次数即可。

主函数：

int main()
{
 int n,t=0;cin>>n;
 for(int i=0;i<n;i+=1){
  cin>>a[i].n;
  a[i].k=i;
 }
 sort(a,a+n,cmp);
 for(int i=0;i<n;i+=1)
  t=max(t,a[i].k-i); //找出向左交换次数最多的数
 cout<<t+1; //即使排好序也要再进行一次外层循环
 return 0;
}

排序函数：

bool cmp(Num a,Num b){
 if(a.n!=b.n) return a.n<b.n;
 return a.k<b.k;
}

结构体：

struct Num{
 int n,k;
}a[100001];

1

1