题解：CF435B Pasha Maximizes

分析

这个问题是通过有限次数的相邻交换，让给定的数字尽可能大。关键在于如何分配这有限的交换次数，获得最大的数值提升。所以可以用贪心算法来解决。

思路

从左到右遍历每一位数字。
在当前位置 $i$ 和后面的 $k$ 个位置范围内，找到最大的数字。
将找到的最大数字相邻交换移动到位置 $i$ ，交换一次减少一次 $k$ 。
处理下一个位置，直到用完所有交换次数或处理完所有的位置。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int main() {
    string a;
    int k;
    cin >> a >> k;
    int n = a.length();//在循环前算好n，可以节省复杂度。 
    for (int i = 0; i < n && k > 0; i++) {
        int maxx = i;
        for (int j = i + 1; j <= i + k && j < n; j++) {// 找出从位置i到i+k范围内的最大数字
            if (a[j] > a[maxx]) {
                maxx = j;
            }
        }
        
        
        for (int j = maxx; j > i; j--) {// 将最大数字移到当前位置i
            swap(a[j], a[j-1]);//交换 
            k--;//k减少一次 
            if (k == 0)
                break;
        }
    }
    
    cout << a << endl;//答案 
    
    return 0;
}

复杂度分析

时间复杂度：最坏情况下为 $O (n^2)$ 。因为在最坏情况下，每次都需要遍历 $k$ 个位置并进行 $k$ 次交换。
空间复杂度： $O (n)$ ，用于字符串表示。

题解：CF435B Pasha Maximizes

文章操作

分析

思路

代码

复杂度分析

相关推荐

评论

题解：CF435B Pasha Maximizes