洛谷-P1323 删数问题（基础贪心）

题目描述

一个集合有如下元素：11 是集合元素；若 PP 是集合的元素，则 2\times P+12×P+1，4\times P+54×P+5 也是集合的元素。

取出此集合中最小的 kk 个元素，按从小到大的顺序组合成一个多位数，现要求从中删除 mm 个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。

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

输入格式

只有一行两个整数，分别代表 kk 和 mm。

输出格式

输出为两行两个整数，第一行为删除前的数字，第二行为删除后的数字。

输入输出样例

输入 #1

5 4

输出 #1

137915
95

说明/提示

数据规模与约定

• 对于 30\%30% 的数据，保证 1\le k,m\le3001≤k,m≤300。
• 对于 100\%100% 的数据，保证 1\le k,m\le3\times10^41≤k,m≤3×104。

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

int k, m;

string generate()
{
    priority_queue<int, vector<int>, greater<int> > pq;
    pq.push(1);
    int cnt = 0;
    string res;

    while (cnt < m) {
        res += to_string(pq.top());
        int tmp = pq.top(); pq.pop();
        pq.push(2 * tmp + 1);
        pq.push(4 * tmp + 5);
        ++cnt;
    }   

    return res;
}

void removeLetter()
{
    string s = generate();
    cout << s << endl;

    int cnt = 0;
    while (cnt < k) {
        ++cnt;

        int n = s.size();
        bool haveDel = false;
        //从高位往低位找升序数对
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] - '0' < s[i + 1] - '0') {
                haveDel = true;
                s = s.substr(0, i) + s.substr(i + 1);
                break;
            }
        }
        //如果序列降序，删除末尾的数字
        if (!haveDel) s = s.substr(0, n - 1);
    }
    //去除前导零
    int pos = 0, n = s.size();
    while (pos < n - 1) {
        if (s[pos] - '0' == 0) ++pos;
        else break;
    }

    cout << s.substr(pos) << endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> m >> k;
    removeLetter();

    return 0;
}

额外需要注意的是集合生成的过程，最终是想使用一个set来生成数据，想让集合的大小超过k即可。但是可以换一种思路，用一个优先级队列，只要取出的数字为m个就可以停止了。至于删除数字的过程，和之前删除数字使最小的思路使一样的，就不再赘述了。