首页 > 试题广场 >

冒泡排序

[编程题]冒泡排序

热度指数：1875 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。

BubbleSort(a):
    Repeat length(a)-1 times:
        For every i from 0 to length(a) - 2:
            If a[i] > a[i+1] then:
                 Swap a[i] and a[i+1]

牛牛现在要使用上述算法对一个数组A排序。
在排序前牛牛允许执行最多k次特定操作(可以不使用完),每次特定操作选择一个连续子数组,然后对其进行翻转,并且k次特定操作选择的子数组不相交。
例如A = {1, 2, 3, 4, 5, 6, 7}, k = 1,如果牛牛选择的子数组是[2,4](注意下标从0开始),那么翻转之后的数组变为A = {1, 2, 5, 4, 3, 6, 7}。
牛牛知道冒泡排序的效率一定程度上取决于Swap操作次数,牛牛想知道对于一个数组A在进行k次特定操作之后,再进行上述冒泡排序最少的Swap操作次数是多少?

输入描述:

输入包括两行,第一行包括两个正整数n和k(2 ≤ n ≤ 50, 1 ≤ k ≤ 50),表示数组的长度和允许最多的特定操作次数。
第二行n个正整数A[i](1 ≤ A[i] ≤ 1000),表示数组内的元素,以空格分割。

输出描述:

输出一个整数,表示在执行最多k次特定操作之后,对数组进行上述冒泡排序需要的Swap操作次数。

示例1

输入

3 2
2 3 1

输出

算法知识视频讲解

Java

头脑风暴_

#采用区间动态规划的思想，具体请参考

https://www.cnblogs.com/***allJunJun/p/10885114.html

public clas***ain1 {
    public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);             
           int n=sc.nextInt();             
           int k=sc.nextInt();             
           int[] a=new int[n];             
           for(int i=0;i<n;i++)         
               a[i]=sc.nextInt();   
            int[][]dp =new int[n+1][k+1];//表示前i个数总共旋转j次最多能够减少的逆序数对       
           for(int i=2;i<=n;i++) {         
                 for(int j=1;j<=k;j++) {             
                    int temp=Integer.MIN_VALUE;             
                    for(int t=i-1;t>=1;t--) {               temp=Math.max(countReverseBefore(a,t-1,i-1)-countReverseAfter(a,t-1,i-1)+dp[t-1][j-1], temp);             }             
                    dp[i][j]=Math.max(dp[i-1][j], temp);  
            }    
          }       
           System.out.println(countReverseBefore(a,0,n-1)-dp[n][k]);

     }
   private static int countReverseBefore(int[] arr, int begin, int end) {  
       int count = 0;        
          for (int i = begin; i <= end; i++) {  
          for (int j = i+1; j <= end; j++) {   
             if (arr[j] < arr[i]) 
                         count++;                 
                 }        
          }             
            return count;
   }

   private static int countReverseAfter(int[] arr, int begin, int end) {
        int count = 0;
        for (int i = end; i >= begin; i--) {
            for (int j = i-1; j >=begin; j--) {
                if (arr[j] < arr[i]) count++;
            }
        }
        return count;
   }
}