题解：CF435B Pasha Maximizes

zhangmuning1016 · 2025-05-20 14:40:02 · 题解

分析

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

思路

• 从左到右遍历每一位数字。
• 在当前位置 i 和后面的 k 个位置范围内，找到最大的数字。
• 将找到的最大数字相邻交换移动到位置 i，交换一次减少一次 k。

• 处理下一个位置，直到用完所有交换次数或处理完所有的位置。

  代码

  #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)，用于字符串表示。