Pasha Maximizes CodeForces - 435B 【字符串处理+贪心思想】

题意：已知一个数n,当前可以执行k次操作，每次操作可以更换相邻两个数字。要求输出k次操作后，所能得到的最大数。

思路：字符串处理。 对于当前的 str[i],我们在[i+1,i+index]的范围内取寻找比str[i]要大的数字，然后交换

数据分析：1 ≤ n ≤ 1e18; 0 ≤ k ≤ 100 .（别以为1e18就开LONG LONG，不过还是要想到）

复杂度分析：设字符串长度为len ， 复杂度为O(len^2)

错误分析：WA了一次，第一次的思路是，对于当前的str[i],如果str[i+1]>str[i]， 就swap 。 结果wa在第五组。 后来仔细思考了一下，发现是有问题的.

#include <bits/stdc++.h>
using namespace std;
char str[100];
int main(void)
{
    scanf("%s",str+1);
    int k;
    cin >>k;
    for(int i=1; i<strlen(str+1); i++)
    {

        char mmax=str[i];
        int index=-1;
        //找比str[i]大的[i+1,i+index]范围内的最大值。
        for(int j=i+1; j<=i+k && j<=strlen(str+1); j++)
        {
            if(str[j] > mmax)
            {
                index=j,mmax=str[j];
            }
        }
        if(index==-1)   continue; // 如果没找到，则不交换,continue
        for(int o=index; o>=i+1; o--)
        {
            swap(str[o],str[o-1]);
        }
        k-=(index-i); if(k==0) break;

    }
    cout << (str+1) << endl;
}