题解：P1116 车厢重组

题目传送门

题意概括

输入一个序列

a

，要求求出将序列

a

从小到大排序的次数。

分析

标准逆序对。
如果

a_i>a_j

且

i<j

，则这两个数称为逆序数。
利用冒泡排序，由于

n \le 10000

，复杂度为

O(n^2)

，所以不会超时。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int n,t,s=0,a[10001];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n-1;i++){
	        for(int j=1;j<=n-i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				s++;
			}
		}
	}
	cout<<s;
	return 0;
}

注意

不要超题解。~~本蒟蒻就是超题解棕名的~~

球球了

能通过吗 QWQ

题解：P1116 车厢重组

文章操作

题目传送门

题意概括

分析

代码

相关推荐

评论

题解：P1116 车厢重组