描述

给出一个无序数列，每次只能交换相邻两个元素，求将原数列变成递增数列的最少交换次数。 如：数列：2,3,1，交换3和1后变成：2,1,3；交换1和2之后变成：1,2,3。总共交换2次。

输入

逗号隔开的正整数数列

输出

正整数

输入样例

2,3,1

输出样例

2

思路：

只能交换相邻的数字的话，本质上就是寻找有多少对逆序数对

AC代码：

#include <bits/stdc++.h>
#include<vector>
using namespace std;

int mySwap(int &a,int &b)
{
    int t;
    t = a;
    a = b;
    b = t;
}

int main()
{
    string s;

    while(cin>>s)
    {
        s = s+",";
        bool flag = false;
        vector<int>a;
        int b = 0;
        int j = 0;
        int k = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] ==',')
            {
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                // cout<<b<<endl;
                j = i+1;
            }
            if(flag == true)
            {
                if(b>0)
                {
                    a.push_back(b);
                }
            }
        }
        int sum = 0;
        for(int i = 0;i<a.size()-1;i++){
            for(int j = i+1;j<a.size();j++){
                if(a[j] < a[i]){
                    sum++;
                }
            }
        }
       cout<<sum<<endl;
    }
}