题目描述

　　桐桐已经是中学生了。她喜欢研究数字，觉得最漂亮的数就是整数了。

　　一次，桐桐写下一个整数（无前导0），她想研究下面这个游戏：每次取其中两位交换，会得到一个新的整数——但不能有前导0出现，即第一位不能变成0.这样连续做m次，最后能得到的最大整数是多少？

 

输入格式

　　一行，两个整数N（1≤N≤1000000）和m（1≤m≤10）。

 

输出格式

　　一行，一个整数，为桐桐变化后的最大数，如果不能变换则输出-1。

 

输入样例一

16375 1

 

输出样例一

76315

 

输入样例二

432 1

 

输出样例二

423

 

输入样例三

90 4

 

输出样例三

-1

 

题解

　　一个比较简单的贪心策略。先看当前的数从最高位到最低位是否不上升，如果不上升就换相同的数字，否则换最后两个数字。

　　存在上升子序列的情况就有点麻烦了。

　　我们从最高位开始枚举，设当前为的数字为$a[i]$，那我们需要在$(i,len]$中找满足$a[p]>a[i]$的最大的$a[p]$，更换这两个数字即可。

　　但是，如果有多个$a[p]$怎么办？我们设$(i,len]$中比$a[i]$大的$a[j]$的数量为$cnt$，和当前枚举到的$a[p]$的数量为$same$。

　　假设当前枚举到一个$a[j]$与$a[p]$相等，我们容易想到，如果$same>m$，我们就不需要更新$p$。否则，如果$cnt-same=0$或$cnt-same \geqslant same$，那我们也不需要更新$p$，否则更新$p=j$。

#include 
        
         #include 
         
          using namespace std;char a[10];int len, m;int main(){    cin >> a + 1 >> m;    len = strlen(a + 1);    if(len == 1 || len == 2 && a[2] == '0') return cout << -1, 0;    int f, p, cnt, same;    ++m;    while(--m)    {        f = 1;        for(register int i = 1; i < len; ++i)        {            p = cnt = same = 0;            for(register int j = i + 1; j <= len; ++j)            {                if(a[j] <= a[i]) continue;                ++cnt;                if(a[j] > a[p]) p = j, same = 1;                else if(a[j] == a[p])                {                    ++same;                    if(same > m) continue;                    if(cnt == same || cnt - same >= same) continue;                    p = j;                }            }            if(!p) continue;            f = 0;            swap(a[i], a[p]);            break;        }        if(f)        {            for(register int i = 1; i < len; ++i)            {                if(a[i] == a[i + 1])                 {                    f = 0;                    break;                }            }            if(f) swap(a[len - 1], a[len]);        }        // cout << a + 1 << "\n";    }    cout << a + 1;    return 0;}