解题思路:
一个乱序序列的 逆序数 = 在只允许相邻两个元素交换的条件下,得到有序序列的交换次数
直接求逆序数
把S[i]和s[i+1~n]的元素逐个比较,如果s[i] > s[k] (k∈[i+1,n]) 则逆序数t++ O(n^2)算法
1 #include<iostream>
2 using namespace std;
3 int main(){
4 int t;
5 cin>>t;
6 int p=1;
7 while(t--)
8 {
9 int n,ans=0;
10 cin>>n;
11 int* num=new int[n+1];
12 for(int i=1;i<=n;i++){
13 cin>>num[i];
14 }
15 for(int i=1;i<=n;i++)
16 for(int j=i+1;j<=n;j++)
17 {
18 if(num[i]>num[j]) ans++;
19 }
20 cout<<"Scenario #"<<p<<":"<<endl<<ans<<endl<<endl;
21 p++;
22 delete num;
23 }
24 return 0;
25 }