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

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-22 21:40:14
    编辑于：2022-03-22 21:40:14
    浏览量：727

概述

给一个数字，有 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;
}

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