题解 CF2050D

· · 题解

题意：

给定一个数字串，可以交换相邻两位，但原来靠右的需要 -1，随意操作最大化字符串代表的数字。

思路：

显然一个字符向前交换的次数不会超过 9。对于一个位置，枚举其后十个值即可，所以复杂度非常的低。

对于一个位置，从后十个字符中找到交换到当前位置后答案最大的情况，并且实施操作即可。容易发现这样贪心一定是最优的。

程序如下：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n;
char a[200005];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",a+1);
        n=strlen(a+1);
        for(int i=1;i<=n;i++){
            int curmx=0,curpos=i;
            for(int j=i;j<=i+10&&j<=n;j++){
                if(a[j]-'0'-(j-i)>curmx){
                    curmx=a[j]-'0'-(j-i);
                    curpos=j;
                }
            }
            for(int j=curpos;j>i;j--){
                swap(a[j],a[j-1]);
                a[j-1]--;
            }
        }
        for(int i=1;i<=n;i++)printf("%c",a[i]);
        puts("");
    }
    return 0;
}

THE END