题解：P1106 删数问题

jzl_1210 · 2026-01-17 20:25:05 · 题解

容易想到贪心。

题解

设 n 为这个整数的位数。
把题目转化为选 n-k 个数，那么越前面的数就应该尽量小。若选完这个数后还要选 a 个数，需要注意这个数的位置最大为 n-a。

选完这个数后，再往下选最小的数就可以了。

代码

::::info[满分代码]

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 255;
int k, a[N], n, x, cnt, js;
string s;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> s >> k;
    for(auto i : s) a[++n] = i - '0';
    cnt = n - k;
    for(int i = 1;i <= cnt;i++){
        int minn = 10, mini;
        //找最小值 
        while(x + 1 + (cnt - i) <= n) x++, mini = a[x] < minn ? x : mini, minn = min(minn, a[x]);
        x = mini;
        if(minn == 0 && !js) continue;//注意前导零 
        cout << minn;//输出 
        js++;
    }
    if(!js) cout << 0;//非零数全删完了要输出0 
    return 0;
}

::::