题解 CF2050D

题意：

给定一个数字串，可以交换相邻两位，但原来靠右的需要

-1

，随意操作最大化字符串代表的数字。

思路：

显然一个字符向前交换的次数不会超过

9

。对于一个位置，枚举其后十个值即可，所以复杂度非常的低。

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

程序如下：

CPP

#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

相关推荐

评论

题解 CF2050D