删数问题:贪心/BFS/字符串/优先队列

2023-05-24 09:39:28    动态资讯   

题目描述:删数问题(加强版)

描述:

一个集合有如下元素:1是集合元素;若P是集合的元素,则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K个元素,按从小到大的顺序组合成一个多位数,现要求从中删除M个数位上的数字,使得剩下的数字最大,编程输出删除前和删除后的多位数字。

注:不存在所有数被删除的情况

难度:普及+/提高

题目类型:贪心/模拟

提交次数:3

涉及知识:贪心/BFS/字符串/优先队列

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int a[30010];
char c[10000];
string s;
priority_queue<int, vector<int>, greater<int> > q;
int main(){
    int k, m, i = 0;
    cin>>k>>m;
    q.push(1);
    while(!q.empty()){
        int t = q.top();
        q.push(t*2+1);
        q.push(t*4+5);
        q.pop();
        a[i++] = t;
        if(i==k) break;
    }
    for(i = 0; i < k; i++){
        memset(c, 0, sizeof(c));
       sprintf(c, "%d", a[i]);
        s += c;
   }
    cout<<s<<endl;
//——————————————————————————————————————
    int n = 0;
    i = 0;
    while(n<m&&i<s.length()-1){
        i++;
        if(s[i-1]<s[i]){
            s.erase(i-1,1);
            n++;
            i=0;
        }
    }
    for(i = 0; i < m-n; i++)
        s.erase(s.length()-1, 1);
    for(i = 0; i < s.length(); i++){
        if(s[i]!='0') {
            cout<<s.substr(i, s.length()-i);
            return 0;
        }
    }
    if(i==s.length())cout<<'0';
    return 0;
}