M - Sort it 一组简单一点的题目(三)

末蓝、 2022-02-26 16:56 112阅读 0赞

题目：M - Sort it  
You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.  
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.  
Input  
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.  
Output  
For each case, output the minimum times need to sort it in ascending order on a single line.  
Sample Input  
3  
1 2 3  
4  
4 3 2 1  
Sample Output  
0  
6

大意：就是将输入的数列进行升序排列的过程中，相邻的两个两两交换的次数最少为多少；

思路：这个题不能单纯的用什么冒泡啥的，显然不行，而是求出其对应的逆序数的对数，求出之后，有多少对就是进行移动的最少的次数。这是因为对于逆序数的时候你可以先交换相邻的逆序数，最后一定能让不相邻的逆序数变成相邻，然后交换，所以有多少对逆序数就最少移动多少次；

新技巧：对于一个序列移动最少次数的时候，等会了快速排序和sort内部的函数之后就更明白了，现在就先理解在数值上与逆序数的对数相同；（逆序数：以数组为例，两个数组元素比较，下标小的但数值大）；（这里是应用了逆序数与其排序之间的关系，学会联系不同的关系，然后再处理问题的时候进行相应的转化）；

代码：

#include<stdio.h>
    
    int main()
    {
        int i,j,m,n,a[1005];
        while(scanf("%d",&n)!=EOF)
        {
            for(i=0;i<n;i++)
            scanf("%d",&a[i]);
            m=0;
            for(i=0;i<n;i++)
               for(j=i+1;j<n;j++)
               if(a[i]>a[j])
               m++;
            printf("%d\n",m);
        }
        return 0;
    }