题解 | #交换到最大#

分析

非常好题目, 使我的大脑旋转

错误思路: 对于每个位置, 如果发现, 交换

这个是错误的, 因为交换后当前位置还是可以继续向前交换的

正确做法

对于每个位置, 因为只能与右侧的数字进行交换, 假设位置是, 那么交换的条件就是

也就是说需要找到一个最大的

因为每个位置的字符都是数字, 因此范围是

算法时间复杂度

AC代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

void solve() {
    string s;
    cin >> s;
    int n = s.size();

    for (int i = 0; i < n; ++i) {
        int idx = i;
        int val = s[i] - '0';

        for (int j = i + 1; j <= min(9 + i, n); ++j) {
            int cur = (s[j] - '0') - (j - i);
            if (cur > val) {
                val = cur;
                idx = j;
            }
        }

        for (int j = idx; j > i; --j) {
            swap(s[j], s[j - 1]);
            s[j - 1]--;
        }
        s[i] = val + '0';
    }

    cout << s << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}