大致题意
给定一个数字串，可以交换相邻两位，但原来靠右的需要 \(-1\)，随意操作最大化字符串代表的数字。
题目解法
要想让整个数最大，就要让高位上的数尽可能大。但是，若要把一个数向前交换 \(x\) 个位置，这个数就要 \(-x\), 由于每一位上的数都是 \(\le 9\)，所以我们就可以确定，对于每一个数，它最多往前移 \(9\) 个格子。所以，对于每一位，我们考虑将它后面的 \(9\) 个格子上的数移到这个位置上，取这个格子上的数和后面 \(9\) 个格子上的数移到这个位置上的值取最大值。这步操作为常数级别，所以总复杂度为 \(O(n)\)。
下面是代码环节：
#include<bits/stdc++.h>
using namespace std;
int t;
string s;
signed main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> t;while (t --) {cin >> s;int len = s.size();s = " " + s;for (int i = 1; i <= len; i ++) {int maxn = s[i] - '0', num = i;for (int j = 1; j <= 9 && i + j <= len; j ++) {if (maxn < s[i + j] - '0' - j) {maxn = s[i + j] - '0' - j;num = i + j;}}if (num == i) {continue;}for(int j = num; j > i; j --) {swap(s[j], s[j - 1]);}s[i] = maxn + '0'; }for (int i = 1; i <= len; i ++) {cout << s[i];}cout << "\n";}return 0;
}