动态规划冒泡排序爱奇艺2018招聘

缺乏、安全感 2022-03-25 07:08 283阅读 0赞

这次分析一下2018年爱奇艺招聘的冒泡排序的题目。

题目描述：牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组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操作次数。

解题思路：看到题目，首先要思考，交换的次数跟什么有关，通过观察可以看出，冒泡排序的总交换次数等于数组中每一个元素的逆序数对的和，所谓逆序数对就是排在该元素后面而且大于该元素的个数。所以问题就转化为对数组旋转不超过k次的条件下数组所有元素的逆序数对和最小。所以我们每次进行旋转应该尽量使得旋转的数组逆序数对变小。这里我们采用动态规划的思想。用dp\[i\]\[j\]表示前i个数总共旋转j次最多能够减少的逆序数对。那么对于第i + 1个数，可以将前面任意一个数和第i+1个数进行旋转得到减少的逆序数对，也可以不旋转。所以可以得到递推公式：

![\\small dp\[i\]\[j\] = max(dp\[i-1\]\[j\], re\[t\]\[i\] - sh\[t\]\[i\] + dp\[t - 1\]\[j - 1\])(0 \\leqslant t < i)][small dp_i_j_ _ max_dp_i-1_j_ re_t_i_ - sh_t_i_ _ dp_t - 1_j - 1_0 _leqslant t _ i]

这里的re\[t\]\[i\]表示从t到i之间的逆序数对，sh\[t\]\[i\]表示数组t到i的元素旋转后的逆序数对。下面是代码：

#include<iostream>
    #include<vector>
    #include<algorithm>
    #include<climits>
    using namespace std;
    //获得从m到n的逆序数总数
    int  get_re(vector<int> arr, int m, int n){
        int tem = 0;
        for(int i = m; i <= n; i++){
            for(int j = i + 1; j <= n; j++){
                if(arr[j] < arr[i]){
                    tem++;
                }
            }
        }
        return tem;
    }
    //获得从m到n旋转后的逆序数总数
    int get_sh(vector<int> arr, int m, int n){
    	reverse(arr.begin() + m, arr.begin() + n + 1);
        int tem = 0;
        for(int i = m; i <= n; i++){
            for(int j = i + 1; j <= n; j++){
                if(arr[j] < arr[i]){
                    tem++;
                }
            }
    		
        }
        return tem;
    }
    int main(){
        int n;
        int k;
        while(cin >> n >> k){
            vector<int> arr(n + 1, 0);
            vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
            for(int i = 1; i <= n; i++){
                cin >> arr[i];
    		}
            for(int i = 2; i <= n; i++){
                for(int j = 1; j <= k; j++){
                    int tem = INT_MIN;
                    for(int t = i - 1; t >= 1; t--){
                        tem = max(tem, get_re(arr,t,i) - get_sh(arr, t, i) + dp[t - 1][j - 1]);
                    }
                    dp[i][j] = max(dp[i - 1][j], tem);
                }
            }
            cout << get_re(arr, 1, n) - dp[n][k] << endl;
        }
        return 0;
    }

[small dp_i_j_ _ max_dp_i-1_j_ re_t_i_ - sh_t_i_ _ dp_t - 1_j - 1_0 _leqslant t _ i]: https://private.codecogs.com/gif.latex?%5Csmall%20dp%5Bi%5D%5Bj%5D%20%3D%20max%28dp%5Bi-1%5D%5Bj%5D%2C%20re%5Bt%5D%5Bi%5D%20-%20sh%5Bt%5D%5Bi%5D%20&plus;%20dp%5Bt%20-%201%5D%5Bj%20-%201%5D%29%280%20%5Cleqslant%20t%20%3C%20i%29