洛谷P1106 删数问题

题目传送门：https://www.luogu.com.cn/problem/P1106

解法一：循环k次，每次找逆序对并删除左边的数，如果找不到则说明数列已经是非递减的，直接删最右边的。注意前导零的处理即可。

时间复杂度：$O(kn)$

#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
constexpr int N = 1e5 + 5;
void solve() {
    // 尝试找到第一个相邻逆序对，删除逆序对的左侧数
    // 如果已非降序，删末尾的
    string str;
    cin >> str;
    int n = str.size();
    int k;
    cin >> k;
    auto get_next = [&](int idx) {
        while(++idx < n && str[idx] == '\0');
        return idx;
    };
    while (k--) {
        int l = get_next(-1);
        int r = get_next(l);
        while (r < n && str[l] <= str[r]) {
            l = r;
            r = get_next(r);
        }
        str[l] = '\0';
    }
    string ans;
    for (auto &ch : str) {
        if (ch == '\0') continue;
        ans.push_back(ch);
    }
    if (ans.size() > 1) {
        int i = 0;
        int n = ans.size();
        while (i < n && ans[i] == '0')
            ++i;
        ans = ans.substr(min(i, n-1));
    }
    cout << ans;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    solve();
    return 0;
}

解法二：预处理得到nxt数组，表示右边最近的比arr[i]小的数的下标。

时间复杂度：$O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
mt19937_64 rng(random_device{}());
void solve() {
    string str;
    cin >> str;
    int op; cin >> op;
    int n = str.size();
    // dp[i][j]表示数字i在str中第j次出现的位置
    vector<vector<int>> dp(10);
    // 最近一个比arr[i]小的数的idx
    vector<int> nxt(n, INT_MAX);
    for (int i = 0; i < n; ++i) {
        dp[str[i] - '0'].push_back(i);
    }
    // 避免删除头部数据反复移动所有元素，先reverse一下
    for (int i = 0; i <= 9; ++i)
        reverse(dp[i].begin(), dp[i].end());
    for (int i = 0; i < n; ++i) {
        for (int j = str[i]-'0'-1; j >= 0; --j) {
            auto &vec = dp[j];
            while (!vec.empty() && vec.back() <= i) vec.pop_back();
            if (!vec.empty()) nxt[i] = min(nxt[i], vec.back());
        }
    }
    int i = 0;
    // 表示已删除的位
    vector<bool> del(n);
    // 贪心，优先让前面的数变小
    while (op && i < n) {
        // 至少要删cur个数字才能让当前位置的数减小
        int cur = nxt[i] - i;
        if (cur <= op) {
            op -= cur;
            for (int j = 0; j < cur; ++j) {
                del[i+j] = 1;
            }
            i = nxt[i];
        } else {
            // 删不了，下一个
            ++i;
        }
    }
    // 此时数组已经有序，末尾的数最大，删末尾的
    for (int i = n-1; i >= 0; --i) {
        if (!op) break;
        if (!del[i]) {
            del[i] = 1;
            --op;
        }
    }
    string ans;
    bool heading = true;
    for (int i = 0; i < n; ++i) {
        if (!del[i]) {
            if (heading && str[i] == '0') continue;
            else {
                heading = false;
                ans += str[i];   
            }
        }
    }
    if (ans.empty()) ans.push_back('0');
    cout << ans << '\n';
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) 
        solve();
    return 0;
}