寻找最大数——模拟

题目描述
给出一个正整数N，每次可以移动2个相邻数位上的数字，最多移动K次，得到一个新的正整数。求这个新的正整数的最大值。
输入
输入一个正整数N和K，输出新的正整数。例如：N=1990，K=1，输出9190；N=101，K=0，输出101；N= 9090000078001234，K= 6，输出9907000008001234。
输出
输出新的数字

样例输入
1990 1
101 0
9090000078001234 6
样例输出
9190
101
9907000008001234

String是属于c++的类，String定义的字符串不能用scanf，printf输入输出，但可以使用，cin，cout输入输出，也可以用getline（cin，s）输入

题目分析

1. 题目要有经过有限次相邻两个数交换后，要求得出最大的数
2. 首先交换次数k已经给定，所以我们要尽量让这个数的高位变大，所以我们从左至右一次遍历把最大的数记下来用于交换，我们每次只能做相邻的两个数交换，而不是只交换最大的数和第一个数。
3. 如果我们找到了最大的数标记为t，因为我们是从i开始遍历的，所以交换的次数就是t-i。
4. 还有一个要注意的地方，就是在内层循环中，j的最大值不能超过字符串本身的长度，不然会越界产生无法想象的结果

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
   
   string s;
   int k, t;
   while (cin >> s >> k)
   {
   
      int m = s.length();
      for (int i = 0; i < m && k != 0; ++i)
      {
   
         t = i;
         for (int j = i + 1; j <= i + k && j < m; ++j)
            if (s[t] < s[j])
               t = j;
         for (int j = t; j > i; --j)
            swap(s[j], s[j - 1]);
         k -= (t - i);
      }
      cout << s << endl;
   }
   return 0;
}

字符数组AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int main()
{
   
   char c[maxn];
   int k, t;
   while (~scanf("%s%d", c, &k))
   {
   
      int lc = strlen(c);
      for (int i = 0; i < lc && k != 0; ++i)
      {
   
         t = i;
         for (int j = i + 1; j <= i + k && j < lc; ++j)
         {
   
            if (c[t] < c[j])
               t = j;
         }
         for (int j = t; j > i; --j)
            swap(c[j], c[j - 1]);
         k -= (t - i);
      }
      printf("%s\n", c);
   }
   return 0;
}

初夏的清晨总是让人心旷神怡~