去除 n 位数字中的 k 位并使剩下的数字最大

Tag: 笔试算法题 Posted on 2022-03-22 21:40:14 Edited on 2022-03-22 21:40:14 Views: 147

概述

给一个数字,有 n 位,让你去除其中的 k 位,使剩下的最大

贪心

WA,36%

#include <bits/stdc++.h>
using namespace std;

int main() {
    int num; cin >> num;
    string s = to_string(num);
    int n = s.size();
    int k = s[0] - '0';
    int l = n - k;
    int lastK = -1;
    vector<bool> removed(n, false);
    while (k != lastK) {
        lastK = k;
        int last = 0;
        for (int i = 1; i < n - 1; i ++) {
            if (k == 0) break;
            if (removed[i]) continue;
            if (!removed[last]) {
                if (s[last] < s[i]) {
                    removed[last] = true;
                    k --;
                    break;
                }
            }
            last = i;
        }
        if (k == 0) break;
    }
    int ans = 0;
    for (int i = 0; i < n; i ++) {
        if (l == 0) break;
        if (!removed[i]) {
            ans *= 10;
            ans += s[i] - '0';
            l --;
        }
    }
    cout << ans << endl;
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/