删数问题

题目描述

键盘输入一个高精度的正整数 \(N\)（不超过 \(250\) 位），去掉其中任意 \(k\) 个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 \(N\) 和 \(k\)，寻找一种方案使得剩下的数字组成的新数最小。

输入格式

输入两行正整数。

第一行输入一个高精度的正整数 \(n\)。

第二行输入一个正整数 \(k\)，表示需要删除的数字个数。

输出格式

输出一个整数，最后剩下的最小数。

样例 #1

样例输入 #1

175438 
4

样例输出 #1

13

题解1

规律：
4：
1 4 1 5 1 9
留 删 留 删 留 留
2：
1 5 1 9
留 删 留 删

会发现我们删除的是一个山峰，也就是比后一个数要大的数，且越靠前的山峰
基本思路：删除靠前的“山峰”，执行k次

Tips： 注意最后要删前缀0

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e5+5; 

string s;
int n;

int main() {
    cin >> s >> n;
    int len = SZ(s);
    while(n--) {
        for(int i = 1; i < len; i++) {
            if(s[i] < s[i-1]) {
                for(int j = i; j < len; j++) {
                    s[j-1] = s[j];
                }
                break;
            }
        }
        len--;
    }
    int i = 0;
    while(i <= len-1 && s[i] == '0') {
        i++;
    } 
    if(i == len) {
        cout << "0\n";
        return 0;
    }
    for(; i < len; i++) {
        cout << s[i];
    }
    return 0;
}

题解2

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e5+5; 

int n;
string s;
char c[200];    

int main() {
    cin >> s >> n;
    int len = SZ(s);        
    int k = -1;             // 上一个选的数的位置
    int cnt = 0;            // 已经选的个数
    int sy = len - n;       // 挑选sy个数
    while(sy-cnt!=0) {   
        int minn = INT_MAX;
        for(int i = k+1; i <= len-sy+cnt; i++) {         //每次选一个最小的数且位置最靠前
            if(s[i] < minn) {
                minn = s[i];
                k = i;
            }
        }
        c[cnt++] = s[k];
    }
    int i = 0;
    while(sy - i - 1 != 0 && c[i] == '0') i++;
    for(; i < cnt; i++) {
        cout << c[i];
    }
    cout << "\n";
    return 0;
}